From b462361dbedb1ebaa76fdeddacca562e9d86a956 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Wed, 27 Jul 2016 21:58:47 -0700 Subject: 3154 - reorg before making 'random' more testable --- 065duplex_list.mu | 559 ++++++++++++++++++++++++++++++++++++++++++++++++ 065random.cc | 62 ------ 066duplex_list.mu | 559 ------------------------------------------------ 066stream.mu | 64 ++++++ 067random.cc | 62 ++++++ 067stream.mu | 64 ------ 068hash.cc | 381 --------------------------------- 069hash.cc | 381 +++++++++++++++++++++++++++++++++ 069table.mu | 87 -------- 070recipe.cc | 249 ---------------------- 070table.mu | 87 ++++++++ 071recipe.cc | 249 ++++++++++++++++++++++ 071scheduler.cc | 625 ------------------------------------------------------ 072scheduler.cc | 625 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 072wait.cc | 329 ---------------------------- 073deep_copy.cc | 387 --------------------------------- 073wait.cc | 329 ++++++++++++++++++++++++++++ 074channel.mu | 452 --------------------------------------- 074deep_copy.cc | 387 +++++++++++++++++++++++++++++++++ 075channel.mu | 452 +++++++++++++++++++++++++++++++++++++++ 20 files changed, 3195 insertions(+), 3195 deletions(-) create mode 100644 065duplex_list.mu delete mode 100644 065random.cc delete mode 100644 066duplex_list.mu create mode 100644 066stream.mu create mode 100644 067random.cc delete mode 100644 067stream.mu delete mode 100644 068hash.cc create mode 100644 069hash.cc delete mode 100644 069table.mu delete mode 100644 070recipe.cc create mode 100644 070table.mu create mode 100644 071recipe.cc delete mode 100644 071scheduler.cc create mode 100644 072scheduler.cc delete mode 100644 072wait.cc delete mode 100644 073deep_copy.cc create mode 100644 073wait.cc delete mode 100644 074channel.mu create mode 100644 074deep_copy.cc create mode 100644 075channel.mu diff --git a/065duplex_list.mu b/065duplex_list.mu new file mode 100644 index 00000000..cefab1f8 --- /dev/null +++ b/065duplex_list.mu @@ -0,0 +1,559 @@ +# A doubly linked list permits bidirectional traversal. + +container duplex-list:_elem [ + value:_elem + next:address:duplex-list:_elem + prev:address:duplex-list:_elem +] + +# should I say in/contained-in:result, allow ingredients to refer to products? +def push x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [ + local-scope + load-ingredients + result:address:duplex-list:_elem <- new {(duplex-list _elem): type} + *result <- merge x, in, 0 + { + break-unless in + *in <- put *in, prev:offset, result + } + return result # needed explicitly because we need to replace 'in' with 'result' +] + +def first in:address:duplex-list:_elem -> result:_elem [ + local-scope + load-ingredients + return-unless in, 0 + result <- get *in, value:offset +] + +def next in:address:duplex-list:_elem -> result:address:duplex-list:_elem/contained-in:in [ + local-scope + load-ingredients + return-unless in, 0 + result <- get *in, next:offset +] + +def prev in:address:duplex-list:_elem -> result:address:duplex-list:_elem/contained-in:in [ + local-scope + load-ingredients + return-unless in, 0 + result <- get *in, prev:offset + return result +] + +scenario duplex-list-handling [ + run [ + local-scope + # reserve locations 0-9 to check for missing null check + 10:number/raw <- copy 34 + 11:number/raw <- copy 35 + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + list2:address:duplex-list:character <- copy list + 20:character/raw <- first list2 + list2 <- next list2 + 21:character/raw <- first list2 + list2 <- next list2 + 22:character/raw <- first list2 + 30:address:duplex-list:character/raw <- next list2 + 31:character/raw <- first 30:address:duplex-list:character/raw + 32:address:duplex-list:character/raw <- next 30:address:duplex-list:character/raw + 33:address:duplex-list:character/raw <- prev 30:address:duplex-list:character/raw + list2 <- prev list2 + 40:character/raw <- first list2 + list2 <- prev list2 + 41:character/raw <- first list2 + 50:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 0 <- 0 # no modifications to null pointers + 10 <- 34 + 11 <- 35 + 20 <- 5 # scanning next + 21 <- 4 + 22 <- 3 + 30 <- 0 # null + 31 <- 0 # first of null + 32 <- 0 # next of null + 33 <- 0 # prev of null + 40 <- 4 # then start scanning prev + 41 <- 5 + 50 <- 1 # list back at start + ] +] + +# insert 'x' after 'in' +def insert x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [ + local-scope + load-ingredients + new-node:address:duplex-list:_elem <- new {(duplex-list _elem): type} + *new-node <- put *new-node, value:offset, x + # save old next before changing it + next-node:address:duplex-list:_elem <- get *in, next:offset + *in <- put *in, next:offset, new-node + *new-node <- put *new-node, prev:offset, in + *new-node <- put *new-node, next:offset, next-node + return-unless next-node + *next-node <- put *next-node, prev:offset, new-node +] + +scenario inserting-into-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + list2:address:duplex-list:character <- next list # inside list + list2 <- insert 6, list2 + # check structure like before + list2 <- copy list + 10:character/raw <- first list2 + list2 <- next list2 + 11:character/raw <- first list2 + list2 <- next list2 + 12:character/raw <- first list2 + list2 <- next list2 + 13:character/raw <- first list2 + list2 <- prev list2 + 20:character/raw <- first list2 + list2 <- prev list2 + 21:character/raw <- first list2 + list2 <- prev list2 + 22:character/raw <- first list2 + 30:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 5 # scanning next + 11 <- 4 + 12 <- 6 # inserted element + 13 <- 3 + 20 <- 6 # then prev + 21 <- 4 + 22 <- 5 + 30 <- 1 # list back at start + ] +] + +scenario inserting-at-end-of-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + list2:address:duplex-list:character <- next list # inside list + list2 <- next list2 # now at end of list + list2 <- insert 6, list2 + # check structure like before + list2 <- copy list + 10:character/raw <- first list2 + list2 <- next list2 + 11:character/raw <- first list2 + list2 <- next list2 + 12:character/raw <- first list2 + list2 <- next list2 + 13:character/raw <- first list2 + list2 <- prev list2 + 20:character/raw <- first list2 + list2 <- prev list2 + 21:character/raw <- first list2 + list2 <- prev list2 + 22:character/raw <- first list2 + 30:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 5 # scanning next + 11 <- 4 + 12 <- 3 + 13 <- 6 # inserted element + 20 <- 3 # then prev + 21 <- 4 + 22 <- 5 + 30 <- 1 # list back at start + ] +] + +scenario inserting-after-start-of-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + list <- insert 6, list + # check structure like before + list2:address:duplex-list:character <- copy list + 10:character/raw <- first list2 + list2 <- next list2 + 11:character/raw <- first list2 + list2 <- next list2 + 12:character/raw <- first list2 + list2 <- next list2 + 13:character/raw <- first list2 + list2 <- prev list2 + 20:character/raw <- first list2 + list2 <- prev list2 + 21:character/raw <- first list2 + list2 <- prev list2 + 22:character/raw <- first list2 + 30:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 5 # scanning next + 11 <- 6 # inserted element + 12 <- 4 + 13 <- 3 + 20 <- 4 # then prev + 21 <- 6 + 22 <- 5 + 30 <- 1 # list back at start + ] +] + +# remove 'x' from its surrounding list 'in' +# +# Returns null if and only if list is empty. Beware: in that case any other +# pointers to the head are now invalid. +def remove x:address:duplex-list:_elem/contained-in:in, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [ + local-scope + load-ingredients + # if 'x' is null, return + return-unless x + next-node:address:duplex-list:_elem <- get *x, next:offset + prev-node:address:duplex-list:_elem <- get *x, prev:offset + # null x's pointers + *x <- put *x, next:offset, 0 + *x <- put *x, prev:offset, 0 + # if next-node is not null, set its prev pointer + { + break-unless next-node + *next-node <- put *next-node, prev:offset, prev-node + } + # if prev-node is not null, set its next pointer and return + { + break-unless prev-node + *prev-node <- put *prev-node, next:offset, next-node + return + } + # if prev-node is null, then we removed the head node at 'in' + # return the new head rather than the old 'in' + return next-node +] + +scenario removing-from-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + list2:address:duplex-list:character <- next list # second element + list <- remove list2, list + 10:boolean/raw <- equal list2, 0 + # check structure like before + list2 <- copy list + 11:character/raw <- first list2 + list2 <- next list2 + 12:character/raw <- first list2 + 20:address:duplex-list:character/raw <- next list2 + list2 <- prev list2 + 30:character/raw <- first list2 + 40:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 0 # remove returned non-null + 11 <- 5 # scanning next, skipping deleted element + 12 <- 3 + 20 <- 0 # no more elements + 30 <- 5 # prev of final element + 40 <- 1 # list back at start + ] +] + +scenario removing-from-start-of-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + list <- remove list, list + # check structure like before + list2:address:duplex-list:character <- copy list + 10:character/raw <- first list2 + list2 <- next list2 + 11:character/raw <- first list2 + 20:address:duplex-list:character/raw <- next list2 + list2 <- prev list2 + 30:character/raw <- first list2 + 40:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 4 # scanning next, skipping deleted element + 11 <- 3 + 20 <- 0 # no more elements + 30 <- 4 # prev of final element + 40 <- 1 # list back at start + ] +] + +scenario removing-from-end-of-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- push 4, list + list <- push 5, list + # delete last element + list2:address:duplex-list:character <- next list + list2 <- next list2 + list <- remove list2, list + 10:boolean/raw <- equal list2, 0 + # check structure like before + list2 <- copy list + 11:character/raw <- first list2 + list2 <- next list2 + 12:character/raw <- first list2 + 20:address:duplex-list:character/raw <- next list2 + list2 <- prev list2 + 30:character/raw <- first list2 + 40:boolean/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 0 # remove returned non-null + 11 <- 5 # scanning next, skipping deleted element + 12 <- 4 + 20 <- 0 # no more elements + 30 <- 5 # prev of final element + 40 <- 1 # list back at start + ] +] + +scenario removing-from-singleton-duplex-list [ + run [ + local-scope + list:address:duplex-list:character <- push 3, 0 + list <- remove list, list + 1:number/raw <- copy list + ] + memory-should-contain [ + 1 <- 0 # back to an empty list + ] +] + +# remove values between 'start' and 'end' (both exclusive). +# also clear pointers back out from start/end for hygiene. +# set end to 0 to delete everything past start. +# can't set start to 0 to delete everything before end, because there's no +# clean way to return the new head pointer. +def remove-between start:address:duplex-list:_elem, end:address:duplex-list:_elem/contained-in:start -> start:address:duplex-list:_elem [ + local-scope + load-ingredients + next:address:duplex-list:_elem <- get *start, next:offset + nothing-to-delete?:boolean <- equal next, end + return-if nothing-to-delete? + assert next, [malformed duplex list] + # start->next->prev = 0 + # start->next = end + *next <- put *next, prev:offset, 0 + *start <- put *start, next:offset, end + return-unless end + # end->prev->next = 0 + # end->prev = start + prev:address:duplex-list:_elem <- get *end, prev:offset + assert prev, [malformed duplex list - 2] + *prev <- put *prev, next:offset, 0 + *end <- put *end, prev:offset, start +] + +scenario remove-range [ + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + local-scope + list:address:duplex-list:character <- push 18, 0 + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + 1:address:duplex-list:character/raw <- copy list # save list + run [ + local-scope + list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list + # delete 16 onwards + # first pointer: to the third element + list2:address:duplex-list:character <- next list + list2 <- next list2 + list2 <- remove-between list2, 0 + # now check the list + 10:character/raw <- get *list, value:offset + list <- next list + 11:character/raw <- get *list, value:offset + list <- next list + 12:character/raw <- get *list, value:offset + 20:address:duplex-list:character/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 15 + 20 <- 0 + ] +] + +scenario remove-range-to-final [ + local-scope + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + list:address:duplex-list:character <- push 18, 0 + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + 1:address:duplex-list:character/raw <- copy list # save list + run [ + local-scope + list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list + # delete 15, 16 and 17 + # start pointer: to the second element + list2:address:duplex-list:character <- next list + # end pointer: to the last (sixth) element + end:address:duplex-list:character <- next list2 + end <- next end + end <- next end + end <- next end + remove-between list2, end + # now check the list + 10:character/raw <- get *list, value:offset + list <- next list + 11:character/raw <- get *list, value:offset + list <- next list + 12:character/raw <- get *list, value:offset + 20:address:duplex-list:character/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 18 + 20 <- 0 # no more elements + ] +] + +scenario remove-range-empty [ + local-scope + # construct a duplex list with three elements [13, 14, 15] + list:address:duplex-list:character <- push 15, 0 + list <- push 14, list + list <- push 13, list + 1:address:duplex-list:character/raw <- copy list # save list + run [ + local-scope + list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list + # delete between first and second element (i.e. nothing) + list2:address:duplex-list:character <- next list + remove-between list, list2 + # now check the list + 10:character/raw <- get *list, value:offset + list <- next list + 11:character/raw <- get *list, value:offset + list <- next list + 12:character/raw <- get *list, value:offset + 20:address:duplex-list:character/raw <- next list + ] + # no change + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 15 + 20 <- 0 + ] +] + +scenario remove-range-to-end [ + local-scope + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + list:address:duplex-list:character <- push 18, 0 + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + 1:address:duplex-list:character/raw <- copy list # save list + run [ + local-scope + list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list + # remove the third element and beyond + list2:address:duplex-list:character <- next list + remove-between list2, 0 + # now check the list + 10:character/raw <- get *list, value:offset + list <- next list + 11:character/raw <- get *list, value:offset + 20:address:duplex-list:character/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 20 <- 0 + ] +] + +# insert list beginning at 'new' after 'in' +def insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [ + local-scope + load-ingredients + return-unless in + return-unless start + end:address:duplex-list:_elem <- copy start + { + next:address:duplex-list:_elem <- next end/insert-range + break-unless next + end <- copy next + loop + } + next:address:duplex-list:_elem <- next in + *end <- put *end, next:offset, next + { + break-unless next + *next <- put *next, prev:offset, end + } + *in <- put *in, next:offset, start + *start <- put *start, prev:offset, in +] + +def append in:address:duplex-list:_elem, new:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [ + local-scope + load-ingredients + last:address:duplex-list:_elem <- last in + *last <- put *last, next:offset, new + return-unless new + *new <- put *new, prev:offset, last +] + +def last in:address:duplex-list:_elem -> result:address:duplex-list:_elem [ + local-scope + load-ingredients + result <- copy in + { + next:address:duplex-list:_elem <- next result + break-unless next + result <- copy next + loop + } +] + +# helper for debugging +def dump-from x:address:duplex-list:_elem [ + local-scope + load-ingredients + $print x, [: ] + { + break-unless x + c:_elem <- get *x, value:offset + $print c, [ ] + x <- next x + { + is-newline?:boolean <- equal c, 10/newline + break-unless is-newline? + $print 10/newline + $print x, [: ] + } + loop + } + $print 10/newline, [---], 10/newline +] diff --git a/065random.cc b/065random.cc deleted file mode 100644 index 45bcfd7d..00000000 --- a/065random.cc +++ /dev/null @@ -1,62 +0,0 @@ -:(before "End Primitive Recipe Declarations") -RANDOM, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "random", RANDOM); -:(before "End Primitive Recipe Checks") -case RANDOM: { - break; -} -:(before "End Primitive Recipe Implementations") -case RANDOM: { - // todo: limited range of numbers, might be imperfectly random - // todo: thread state in extra ingredients and products - products.resize(1); - products.at(0).push_back(rand()); - break; -} - -:(before "End Primitive Recipe Declarations") -MAKE_RANDOM_NONDETERMINISTIC, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "make-random-nondeterministic", MAKE_RANDOM_NONDETERMINISTIC); -:(before "End Primitive Recipe Checks") -case MAKE_RANDOM_NONDETERMINISTIC: { - break; -} -:(before "End Primitive Recipe Implementations") -case MAKE_RANDOM_NONDETERMINISTIC: { - srand(time(NULL)); - break; -} - -:(before "End Primitive Recipe Declarations") -ROUND, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "round", ROUND); -:(before "End Primitive Recipe Checks") -case ROUND: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'round' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'round' should be a number, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case ROUND: { - products.resize(1); - products.at(0).push_back(rint(ingredients.at(0).at(0))); - break; -} - -:(scenario round_to_nearest_integer) -def main [ - 1:number <- round 12.2 -] -+mem: storing 12 in location 1 - -:(before "End Includes") -#include diff --git a/066duplex_list.mu b/066duplex_list.mu deleted file mode 100644 index cefab1f8..00000000 --- a/066duplex_list.mu +++ /dev/null @@ -1,559 +0,0 @@ -# A doubly linked list permits bidirectional traversal. - -container duplex-list:_elem [ - value:_elem - next:address:duplex-list:_elem - prev:address:duplex-list:_elem -] - -# should I say in/contained-in:result, allow ingredients to refer to products? -def push x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [ - local-scope - load-ingredients - result:address:duplex-list:_elem <- new {(duplex-list _elem): type} - *result <- merge x, in, 0 - { - break-unless in - *in <- put *in, prev:offset, result - } - return result # needed explicitly because we need to replace 'in' with 'result' -] - -def first in:address:duplex-list:_elem -> result:_elem [ - local-scope - load-ingredients - return-unless in, 0 - result <- get *in, value:offset -] - -def next in:address:duplex-list:_elem -> result:address:duplex-list:_elem/contained-in:in [ - local-scope - load-ingredients - return-unless in, 0 - result <- get *in, next:offset -] - -def prev in:address:duplex-list:_elem -> result:address:duplex-list:_elem/contained-in:in [ - local-scope - load-ingredients - return-unless in, 0 - result <- get *in, prev:offset - return result -] - -scenario duplex-list-handling [ - run [ - local-scope - # reserve locations 0-9 to check for missing null check - 10:number/raw <- copy 34 - 11:number/raw <- copy 35 - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - list2:address:duplex-list:character <- copy list - 20:character/raw <- first list2 - list2 <- next list2 - 21:character/raw <- first list2 - list2 <- next list2 - 22:character/raw <- first list2 - 30:address:duplex-list:character/raw <- next list2 - 31:character/raw <- first 30:address:duplex-list:character/raw - 32:address:duplex-list:character/raw <- next 30:address:duplex-list:character/raw - 33:address:duplex-list:character/raw <- prev 30:address:duplex-list:character/raw - list2 <- prev list2 - 40:character/raw <- first list2 - list2 <- prev list2 - 41:character/raw <- first list2 - 50:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 0 <- 0 # no modifications to null pointers - 10 <- 34 - 11 <- 35 - 20 <- 5 # scanning next - 21 <- 4 - 22 <- 3 - 30 <- 0 # null - 31 <- 0 # first of null - 32 <- 0 # next of null - 33 <- 0 # prev of null - 40 <- 4 # then start scanning prev - 41 <- 5 - 50 <- 1 # list back at start - ] -] - -# insert 'x' after 'in' -def insert x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [ - local-scope - load-ingredients - new-node:address:duplex-list:_elem <- new {(duplex-list _elem): type} - *new-node <- put *new-node, value:offset, x - # save old next before changing it - next-node:address:duplex-list:_elem <- get *in, next:offset - *in <- put *in, next:offset, new-node - *new-node <- put *new-node, prev:offset, in - *new-node <- put *new-node, next:offset, next-node - return-unless next-node - *next-node <- put *next-node, prev:offset, new-node -] - -scenario inserting-into-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - list2:address:duplex-list:character <- next list # inside list - list2 <- insert 6, list2 - # check structure like before - list2 <- copy list - 10:character/raw <- first list2 - list2 <- next list2 - 11:character/raw <- first list2 - list2 <- next list2 - 12:character/raw <- first list2 - list2 <- next list2 - 13:character/raw <- first list2 - list2 <- prev list2 - 20:character/raw <- first list2 - list2 <- prev list2 - 21:character/raw <- first list2 - list2 <- prev list2 - 22:character/raw <- first list2 - 30:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 10 <- 5 # scanning next - 11 <- 4 - 12 <- 6 # inserted element - 13 <- 3 - 20 <- 6 # then prev - 21 <- 4 - 22 <- 5 - 30 <- 1 # list back at start - ] -] - -scenario inserting-at-end-of-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - list2:address:duplex-list:character <- next list # inside list - list2 <- next list2 # now at end of list - list2 <- insert 6, list2 - # check structure like before - list2 <- copy list - 10:character/raw <- first list2 - list2 <- next list2 - 11:character/raw <- first list2 - list2 <- next list2 - 12:character/raw <- first list2 - list2 <- next list2 - 13:character/raw <- first list2 - list2 <- prev list2 - 20:character/raw <- first list2 - list2 <- prev list2 - 21:character/raw <- first list2 - list2 <- prev list2 - 22:character/raw <- first list2 - 30:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 10 <- 5 # scanning next - 11 <- 4 - 12 <- 3 - 13 <- 6 # inserted element - 20 <- 3 # then prev - 21 <- 4 - 22 <- 5 - 30 <- 1 # list back at start - ] -] - -scenario inserting-after-start-of-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - list <- insert 6, list - # check structure like before - list2:address:duplex-list:character <- copy list - 10:character/raw <- first list2 - list2 <- next list2 - 11:character/raw <- first list2 - list2 <- next list2 - 12:character/raw <- first list2 - list2 <- next list2 - 13:character/raw <- first list2 - list2 <- prev list2 - 20:character/raw <- first list2 - list2 <- prev list2 - 21:character/raw <- first list2 - list2 <- prev list2 - 22:character/raw <- first list2 - 30:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 10 <- 5 # scanning next - 11 <- 6 # inserted element - 12 <- 4 - 13 <- 3 - 20 <- 4 # then prev - 21 <- 6 - 22 <- 5 - 30 <- 1 # list back at start - ] -] - -# remove 'x' from its surrounding list 'in' -# -# Returns null if and only if list is empty. Beware: in that case any other -# pointers to the head are now invalid. -def remove x:address:duplex-list:_elem/contained-in:in, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [ - local-scope - load-ingredients - # if 'x' is null, return - return-unless x - next-node:address:duplex-list:_elem <- get *x, next:offset - prev-node:address:duplex-list:_elem <- get *x, prev:offset - # null x's pointers - *x <- put *x, next:offset, 0 - *x <- put *x, prev:offset, 0 - # if next-node is not null, set its prev pointer - { - break-unless next-node - *next-node <- put *next-node, prev:offset, prev-node - } - # if prev-node is not null, set its next pointer and return - { - break-unless prev-node - *prev-node <- put *prev-node, next:offset, next-node - return - } - # if prev-node is null, then we removed the head node at 'in' - # return the new head rather than the old 'in' - return next-node -] - -scenario removing-from-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - list2:address:duplex-list:character <- next list # second element - list <- remove list2, list - 10:boolean/raw <- equal list2, 0 - # check structure like before - list2 <- copy list - 11:character/raw <- first list2 - list2 <- next list2 - 12:character/raw <- first list2 - 20:address:duplex-list:character/raw <- next list2 - list2 <- prev list2 - 30:character/raw <- first list2 - 40:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 10 <- 0 # remove returned non-null - 11 <- 5 # scanning next, skipping deleted element - 12 <- 3 - 20 <- 0 # no more elements - 30 <- 5 # prev of final element - 40 <- 1 # list back at start - ] -] - -scenario removing-from-start-of-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - list <- remove list, list - # check structure like before - list2:address:duplex-list:character <- copy list - 10:character/raw <- first list2 - list2 <- next list2 - 11:character/raw <- first list2 - 20:address:duplex-list:character/raw <- next list2 - list2 <- prev list2 - 30:character/raw <- first list2 - 40:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 10 <- 4 # scanning next, skipping deleted element - 11 <- 3 - 20 <- 0 # no more elements - 30 <- 4 # prev of final element - 40 <- 1 # list back at start - ] -] - -scenario removing-from-end-of-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- push 4, list - list <- push 5, list - # delete last element - list2:address:duplex-list:character <- next list - list2 <- next list2 - list <- remove list2, list - 10:boolean/raw <- equal list2, 0 - # check structure like before - list2 <- copy list - 11:character/raw <- first list2 - list2 <- next list2 - 12:character/raw <- first list2 - 20:address:duplex-list:character/raw <- next list2 - list2 <- prev list2 - 30:character/raw <- first list2 - 40:boolean/raw <- equal list, list2 - ] - memory-should-contain [ - 10 <- 0 # remove returned non-null - 11 <- 5 # scanning next, skipping deleted element - 12 <- 4 - 20 <- 0 # no more elements - 30 <- 5 # prev of final element - 40 <- 1 # list back at start - ] -] - -scenario removing-from-singleton-duplex-list [ - run [ - local-scope - list:address:duplex-list:character <- push 3, 0 - list <- remove list, list - 1:number/raw <- copy list - ] - memory-should-contain [ - 1 <- 0 # back to an empty list - ] -] - -# remove values between 'start' and 'end' (both exclusive). -# also clear pointers back out from start/end for hygiene. -# set end to 0 to delete everything past start. -# can't set start to 0 to delete everything before end, because there's no -# clean way to return the new head pointer. -def remove-between start:address:duplex-list:_elem, end:address:duplex-list:_elem/contained-in:start -> start:address:duplex-list:_elem [ - local-scope - load-ingredients - next:address:duplex-list:_elem <- get *start, next:offset - nothing-to-delete?:boolean <- equal next, end - return-if nothing-to-delete? - assert next, [malformed duplex list] - # start->next->prev = 0 - # start->next = end - *next <- put *next, prev:offset, 0 - *start <- put *start, next:offset, end - return-unless end - # end->prev->next = 0 - # end->prev = start - prev:address:duplex-list:_elem <- get *end, prev:offset - assert prev, [malformed duplex list - 2] - *prev <- put *prev, next:offset, 0 - *end <- put *end, prev:offset, start -] - -scenario remove-range [ - # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] - local-scope - list:address:duplex-list:character <- push 18, 0 - list <- push 17, list - list <- push 16, list - list <- push 15, list - list <- push 14, list - list <- push 13, list - 1:address:duplex-list:character/raw <- copy list # save list - run [ - local-scope - list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list - # delete 16 onwards - # first pointer: to the third element - list2:address:duplex-list:character <- next list - list2 <- next list2 - list2 <- remove-between list2, 0 - # now check the list - 10:character/raw <- get *list, value:offset - list <- next list - 11:character/raw <- get *list, value:offset - list <- next list - 12:character/raw <- get *list, value:offset - 20:address:duplex-list:character/raw <- next list - ] - memory-should-contain [ - 10 <- 13 - 11 <- 14 - 12 <- 15 - 20 <- 0 - ] -] - -scenario remove-range-to-final [ - local-scope - # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] - list:address:duplex-list:character <- push 18, 0 - list <- push 17, list - list <- push 16, list - list <- push 15, list - list <- push 14, list - list <- push 13, list - 1:address:duplex-list:character/raw <- copy list # save list - run [ - local-scope - list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list - # delete 15, 16 and 17 - # start pointer: to the second element - list2:address:duplex-list:character <- next list - # end pointer: to the last (sixth) element - end:address:duplex-list:character <- next list2 - end <- next end - end <- next end - end <- next end - remove-between list2, end - # now check the list - 10:character/raw <- get *list, value:offset - list <- next list - 11:character/raw <- get *list, value:offset - list <- next list - 12:character/raw <- get *list, value:offset - 20:address:duplex-list:character/raw <- next list - ] - memory-should-contain [ - 10 <- 13 - 11 <- 14 - 12 <- 18 - 20 <- 0 # no more elements - ] -] - -scenario remove-range-empty [ - local-scope - # construct a duplex list with three elements [13, 14, 15] - list:address:duplex-list:character <- push 15, 0 - list <- push 14, list - list <- push 13, list - 1:address:duplex-list:character/raw <- copy list # save list - run [ - local-scope - list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list - # delete between first and second element (i.e. nothing) - list2:address:duplex-list:character <- next list - remove-between list, list2 - # now check the list - 10:character/raw <- get *list, value:offset - list <- next list - 11:character/raw <- get *list, value:offset - list <- next list - 12:character/raw <- get *list, value:offset - 20:address:duplex-list:character/raw <- next list - ] - # no change - memory-should-contain [ - 10 <- 13 - 11 <- 14 - 12 <- 15 - 20 <- 0 - ] -] - -scenario remove-range-to-end [ - local-scope - # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] - list:address:duplex-list:character <- push 18, 0 - list <- push 17, list - list <- push 16, list - list <- push 15, list - list <- push 14, list - list <- push 13, list - 1:address:duplex-list:character/raw <- copy list # save list - run [ - local-scope - list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw # restore list - # remove the third element and beyond - list2:address:duplex-list:character <- next list - remove-between list2, 0 - # now check the list - 10:character/raw <- get *list, value:offset - list <- next list - 11:character/raw <- get *list, value:offset - 20:address:duplex-list:character/raw <- next list - ] - memory-should-contain [ - 10 <- 13 - 11 <- 14 - 20 <- 0 - ] -] - -# insert list beginning at 'new' after 'in' -def insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [ - local-scope - load-ingredients - return-unless in - return-unless start - end:address:duplex-list:_elem <- copy start - { - next:address:duplex-list:_elem <- next end/insert-range - break-unless next - end <- copy next - loop - } - next:address:duplex-list:_elem <- next in - *end <- put *end, next:offset, next - { - break-unless next - *next <- put *next, prev:offset, end - } - *in <- put *in, next:offset, start - *start <- put *start, prev:offset, in -] - -def append in:address:duplex-list:_elem, new:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [ - local-scope - load-ingredients - last:address:duplex-list:_elem <- last in - *last <- put *last, next:offset, new - return-unless new - *new <- put *new, prev:offset, last -] - -def last in:address:duplex-list:_elem -> result:address:duplex-list:_elem [ - local-scope - load-ingredients - result <- copy in - { - next:address:duplex-list:_elem <- next result - break-unless next - result <- copy next - loop - } -] - -# helper for debugging -def dump-from x:address:duplex-list:_elem [ - local-scope - load-ingredients - $print x, [: ] - { - break-unless x - c:_elem <- get *x, value:offset - $print c, [ ] - x <- next x - { - is-newline?:boolean <- equal c, 10/newline - break-unless is-newline? - $print 10/newline - $print x, [: ] - } - loop - } - $print 10/newline, [---], 10/newline -] diff --git a/066stream.mu b/066stream.mu new file mode 100644 index 00000000..ce0b1788 --- /dev/null +++ b/066stream.mu @@ -0,0 +1,64 @@ +# new type to help incrementally read texts (arrays of characters) +container stream [ + index:number + data:address:array:character +] + +def new-stream s:address:array:character -> result:address:stream [ + local-scope + load-ingredients + result <- new stream:type + *result <- put *result, index:offset, 0 + *result <- put *result, data:offset, s +] + +def rewind in:address:stream -> in:address:stream [ + local-scope + load-ingredients + *in <- put *in, index:offset, 0 +] + +def read in:address:stream -> result:character, in:address:stream [ + local-scope + load-ingredients + idx:number <- get *in, index:offset + s:address:array:character <- get *in, data:offset + len:number <- length *s + at-end?:boolean <- greater-or-equal idx len + reply-if at-end?, 0/nul, in + result <- index *s, idx + idx <- add idx, 1 + *in <- put *in, index:offset, idx +] + +def peek in:address:stream -> result:character [ + local-scope + load-ingredients + idx:number <- get *in, index:offset + s:address:array:character <- get *in, data:offset + len:number <- length *s + at-end?:boolean <- greater-or-equal idx len + reply-if at-end?, 0/nul + result <- index *s, idx +] + +def read-line in:address:stream -> result:address:array:character, in:address:stream [ + local-scope + load-ingredients + idx:number <- get *in, index:offset + s:address:array:character <- get *in, data:offset + next-idx:number <- find-next s, 10/newline, idx + result <- copy-range s, idx, next-idx + idx <- add next-idx, 1 # skip newline + # write back + *in <- put *in, index:offset, idx +] + +def end-of-stream? in:address:stream -> result:boolean [ + local-scope + load-ingredients + idx:number <- get *in, index:offset + s:address:array:character <- get *in, data:offset + len:number <- length *s + result <- greater-or-equal idx, len +] diff --git a/067random.cc b/067random.cc new file mode 100644 index 00000000..45bcfd7d --- /dev/null +++ b/067random.cc @@ -0,0 +1,62 @@ +:(before "End Primitive Recipe Declarations") +RANDOM, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "random", RANDOM); +:(before "End Primitive Recipe Checks") +case RANDOM: { + break; +} +:(before "End Primitive Recipe Implementations") +case RANDOM: { + // todo: limited range of numbers, might be imperfectly random + // todo: thread state in extra ingredients and products + products.resize(1); + products.at(0).push_back(rand()); + break; +} + +:(before "End Primitive Recipe Declarations") +MAKE_RANDOM_NONDETERMINISTIC, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "make-random-nondeterministic", MAKE_RANDOM_NONDETERMINISTIC); +:(before "End Primitive Recipe Checks") +case MAKE_RANDOM_NONDETERMINISTIC: { + break; +} +:(before "End Primitive Recipe Implementations") +case MAKE_RANDOM_NONDETERMINISTIC: { + srand(time(NULL)); + break; +} + +:(before "End Primitive Recipe Declarations") +ROUND, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "round", ROUND); +:(before "End Primitive Recipe Checks") +case ROUND: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'round' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'round' should be a number, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case ROUND: { + products.resize(1); + products.at(0).push_back(rint(ingredients.at(0).at(0))); + break; +} + +:(scenario round_to_nearest_integer) +def main [ + 1:number <- round 12.2 +] ++mem: storing 12 in location 1 + +:(before "End Includes") +#include diff --git a/067stream.mu b/067stream.mu deleted file mode 100644 index ce0b1788..00000000 --- a/067stream.mu +++ /dev/null @@ -1,64 +0,0 @@ -# new type to help incrementally read texts (arrays of characters) -container stream [ - index:number - data:address:array:character -] - -def new-stream s:address:array:character -> result:address:stream [ - local-scope - load-ingredients - result <- new stream:type - *result <- put *result, index:offset, 0 - *result <- put *result, data:offset, s -] - -def rewind in:address:stream -> in:address:stream [ - local-scope - load-ingredients - *in <- put *in, index:offset, 0 -] - -def read in:address:stream -> result:character, in:address:stream [ - local-scope - load-ingredients - idx:number <- get *in, index:offset - s:address:array:character <- get *in, data:offset - len:number <- length *s - at-end?:boolean <- greater-or-equal idx len - reply-if at-end?, 0/nul, in - result <- index *s, idx - idx <- add idx, 1 - *in <- put *in, index:offset, idx -] - -def peek in:address:stream -> result:character [ - local-scope - load-ingredients - idx:number <- get *in, index:offset - s:address:array:character <- get *in, data:offset - len:number <- length *s - at-end?:boolean <- greater-or-equal idx len - reply-if at-end?, 0/nul - result <- index *s, idx -] - -def read-line in:address:stream -> result:address:array:character, in:address:stream [ - local-scope - load-ingredients - idx:number <- get *in, index:offset - s:address:array:character <- get *in, data:offset - next-idx:number <- find-next s, 10/newline, idx - result <- copy-range s, idx, next-idx - idx <- add next-idx, 1 # skip newline - # write back - *in <- put *in, index:offset, idx -] - -def end-of-stream? in:address:stream -> result:boolean [ - local-scope - load-ingredients - idx:number <- get *in, index:offset - s:address:array:character <- get *in, data:offset - len:number <- length *s - result <- greater-or-equal idx, len -] diff --git a/068hash.cc b/068hash.cc deleted file mode 100644 index 457d1f9c..00000000 --- a/068hash.cc +++ /dev/null @@ -1,381 +0,0 @@ -// A universal hash function that can handle objects of any type. -// -// The way it's currently implemented, two objects will have the same hash if -// all their non-address fields (all the way down) expand to the same sequence -// of scalar values. In particular, a container with all zero addresses hashes -// to 0. Hopefully this won't be an issue because we are usually hashing -// objects of a single type in any given hash table. -// -// Based on http://burtleburtle.net/bob/hash/hashfaq.html - -:(before "End Primitive Recipe Declarations") -HASH, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "hash", HASH); -:(before "End Primitive Recipe Checks") -case HASH: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'hash' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case HASH: { - const reagent& input = current_instruction().ingredients.at(0); - products.resize(1); - products.at(0).push_back(hash(0, input)); - break; -} - -//: in all the code below, the intermediate results of hashing are threaded through 'h' - -:(code) -size_t hash(size_t h, reagent/*copy*/ r) { - canonize(r); - if (is_mu_string(r)) // optimization - return hash_mu_string(h, r); - else if (is_mu_address(r)) - return hash_mu_address(h, r); - else if (is_mu_scalar(r)) - return hash_mu_scalar(h, r); - else if (is_mu_array(r)) - return hash_mu_array(h, r); - else if (is_mu_container(r)) - return hash_mu_container(h, r); - else if (is_mu_exclusive_container(r)) - return hash_mu_exclusive_container(h, r); - assert(false); -} - -size_t hash_mu_scalar(size_t h, const reagent& r) { - double input = is_literal(r) ? r.value : get_or_insert(Memory, r.value); - return hash_iter(h, static_cast(input)); -} - -size_t hash_mu_address(size_t h, reagent& r) { - if (r.value == 0) return 0; - trace(9999, "mem") << "location " << r.value << " is " << no_scientific(get_or_insert(Memory, r.value)) << end(); - r.value = get_or_insert(Memory, r.value); - if (r.value != 0) { - trace(9999, "mem") << "skipping refcount at " << r.value << end(); - r.set_value(r.value+1); // skip refcount - } - drop_from_type(r, "address"); - return hash(h, r); -} - -size_t hash_mu_string(size_t h, const reagent& r) { - string input = read_mu_string(get_or_insert(Memory, r.value)); - for (int i = 0; i < SIZE(input); ++i) { - h = hash_iter(h, static_cast(input.at(i))); -//? cerr << i << ": " << h << '\n'; - } - return h; -} - -size_t hash_mu_array(size_t h, const reagent& r) { - int size = get_or_insert(Memory, r.value); - reagent/*copy*/ elem = r; - delete elem.type; - elem.type = copy_array_element(r.type); - for (int i=0, address = r.value+1; i < size; ++i, address += size_of(elem)) { - reagent/*copy*/ tmp = elem; - tmp.value = address; - h = hash(h, tmp); -//? cerr << i << " (" << address << "): " << h << '\n'; - } - return h; -} - -size_t hash_mu_container(size_t h, const reagent& r) { - assert(r.type->value); - type_info& info = get(Type, r.type->value); - int address = r.value; - int offset = 0; - for (int i = 0; i < SIZE(info.elements); ++i) { - reagent/*copy*/ element = element_type(r.type, i); - if (has_property(element, "ignore-for-hash")) continue; - element.set_value(address+offset); - h = hash(h, element); -//? cerr << i << ": " << h << '\n'; - offset += size_of(info.elements.at(i).type); - } - return h; -} - -size_t hash_mu_exclusive_container(size_t h, const reagent& r) { - assert(r.type->value); - int tag = get(Memory, r.value); - reagent/*copy*/ variant = variant_type(r, tag); - // todo: move this error to container definition time - if (has_property(variant, "ignore-for-hash")) - raise << get(Type, r.type->value).name << ": /ignore-for-hash won't work in exclusive containers\n" << end(); - variant.set_value(r.value + /*skip tag*/1); - h = hash(h, variant); - return h; -} - -size_t hash_iter(size_t h, size_t input) { - h += input; - h += (h<<10); - h ^= (h>>6); - - h += (h<<3); - h ^= (h>>11); - h += (h<<15); - return h; -} - -:(scenario hash_container_checks_all_elements) -container foo [ - x:number - y:character -] -def main [ - 1:foo <- merge 34, 97/a - 3:number <- hash 1:foo - return-unless 3:number - 4:foo <- merge 34, 98/a - 6:number <- hash 4:foo - return-unless 6:number - 7:boolean <- equal 3:number, 6:number -] -# hash on containers includes all elements -+mem: storing 0 in location 7 - -:(scenario hash_exclusive_container_checks_all_elements) -exclusive-container foo [ - x:bar - y:number -] -container bar [ - a:number - b:number -] -def main [ - 1:foo <- merge 0/x, 34, 35 - 4:number <- hash 1:foo - return-unless 4:number - 5:foo <- merge 0/x, 34, 36 - 8:number <- hash 5:foo - return-unless 8:number - 9:boolean <- equal 4:number, 8:number -] -# hash on containers includes all elements -+mem: storing 0 in location 9 - -:(scenario hash_can_ignore_container_elements) -container foo [ - x:number - y:character/ignore-for-hash -] -def main [ - 1:foo <- merge 34, 97/a - 3:number <- hash 1:foo - return-unless 3:number - 4:foo <- merge 34, 98/a - 6:number <- hash 4:foo - return-unless 6:number - 7:boolean <- equal 3:number, 6:number -] -# hashes match even though y is different -+mem: storing 1 in location 7 - -//: These properties aren't necessary for hash, they just test that the -//: current implementation works like we think it does. - -:(scenario hash_of_zero_address) -def main [ - 1:address:number <- copy 0 - 2:number <- hash 1:address:number -] -+mem: storing 0 in location 2 - -//: This is probably too aggressive, but we need some way to avoid depending -//: on the precise bit pattern of a floating-point number. -:(scenario hash_of_numbers_ignores_fractional_part) -def main [ - 1:number <- hash 1.5 - 2:number <- hash 1 - 3:boolean <- equal 1:number, 2:number -] -+mem: storing 1 in location 3 - -:(scenario hash_of_array_same_as_string) -def main [ - 10:number <- copy 3 - 11:number <- copy 97 - 12:number <- copy 98 - 13:number <- copy 99 - 2:number <- hash 10:array:number/unsafe - return-unless 2:number - 3:address:array:character <- new [abc] - 4:number <- hash 3:address:array:character - return-unless 4:number - 5:boolean <- equal 2:number, 4:number -] -+mem: storing 1 in location 5 - -:(scenario hash_ignores_address_value) -def main [ - 1:address:number <- new number:type - *1:address:number <- copy 34 - 2:number <- hash 1:address:number - 3:address:number <- new number:type - *3:address:number <- copy 34 - 4:number <- hash 3:address:number - 5:boolean <- equal 2:number, 4:number -] -# different addresses hash to the same result as long as the values the point to do so -+mem: storing 1 in location 5 - -:(scenario hash_ignores_address_refcount) -def main [ - 1:address:number <- new number:type - *1:address:number <- copy 34 - 2:number <- hash 1:address:number - return-unless 2:number - # increment refcount - 3:address:number <- copy 1:address:number - 4:number <- hash 3:address:number - return-unless 4:number - 5:boolean <- equal 2:number, 4:number -] -# hash doesn't change when refcount changes -+mem: storing 1 in location 5 - -:(scenario hash_container_depends_only_on_elements) -container foo [ - x:number - y:character -] -container bar [ - x:number - y:character -] -def main [ - 1:foo <- merge 34, 97/a - 3:number <- hash 1:foo - return-unless 3:number - 4:bar <- merge 34, 97/a - 6:number <- hash 4:bar - return-unless 6:number - 7:boolean <- equal 3:number, 6:number -] -# containers with identical elements return identical hashes -+mem: storing 1 in location 7 - -:(scenario hash_container_depends_only_on_elements_2) -container foo [ - x:number - y:character - z:address:number -] -def main [ - 1:address:number <- new number:type - *1:address:number <- copy 34 - 2:foo <- merge 34, 97/a, 1:address:number - 5:number <- hash 2:foo - return-unless 5:number - 6:address:number <- new number:type - *6:address:number <- copy 34 - 7:foo <- merge 34, 97/a, 6:address:number - 10:number <- hash 7:foo - return-unless 10:number - 11:boolean <- equal 5:number, 10:number -] -# containers with identical 'leaf' elements return identical hashes -+mem: storing 1 in location 11 - -:(scenario hash_container_depends_only_on_elements_3) -container foo [ - x:number - y:character - z:bar -] -container bar [ - x:number - y:number -] -def main [ - 1:foo <- merge 34, 97/a, 47, 48 - 6:number <- hash 1:foo - return-unless 6:number - 7:foo <- merge 34, 97/a, 47, 48 - 12:number <- hash 7:foo - return-unless 12:number - 13:boolean <- equal 6:number, 12:number -] -# containers with identical 'leaf' elements return identical hashes -+mem: storing 1 in location 13 - -:(scenario hash_exclusive_container_ignores_tag) -exclusive-container foo [ - x:bar - y:number -] -container bar [ - a:number - b:number -] -def main [ - 1:foo <- merge 0/x, 34, 35 - 4:number <- hash 1:foo - return-unless 4:number - 5:bar <- merge 34, 35 - 7:number <- hash 5:bar - return-unless 7:number - 8:boolean <- equal 4:number, 7:number -] -# hash on containers includes all elements -+mem: storing 1 in location 8 - -//: An older version that supported only strings. -//: Hash functions are subtle and easy to get wrong, so we keep the old -//: version around and check that the new one is consistent with it. - -:(scenario hash_matches_old_version) -def main [ - 1:address:array:character <- new [abc] - 2:number <- hash 1:address:array:character - 3:number <- hash_old 1:address:array:character - 4:boolean <- equal 2:number, 3:number -] -+mem: storing 1 in location 4 - -:(before "End Primitive Recipe Declarations") -HASH_OLD, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "hash_old", HASH_OLD); -:(before "End Primitive Recipe Checks") -case HASH_OLD: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'hash_old' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_string(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "'hash_old' currently only supports strings (address:array:character), but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case HASH_OLD: { - string input = read_mu_string(ingredients.at(0).at(0)); - size_t h = 0 ; - - for (int i = 0; i < SIZE(input); ++i) { - h += static_cast(input.at(i)); - h += (h<<10); - h ^= (h>>6); - - h += (h<<3); - h ^= (h>>11); - h += (h<<15); - } - - products.resize(1); - products.at(0).push_back(h); - break; -} diff --git a/069hash.cc b/069hash.cc new file mode 100644 index 00000000..457d1f9c --- /dev/null +++ b/069hash.cc @@ -0,0 +1,381 @@ +// A universal hash function that can handle objects of any type. +// +// The way it's currently implemented, two objects will have the same hash if +// all their non-address fields (all the way down) expand to the same sequence +// of scalar values. In particular, a container with all zero addresses hashes +// to 0. Hopefully this won't be an issue because we are usually hashing +// objects of a single type in any given hash table. +// +// Based on http://burtleburtle.net/bob/hash/hashfaq.html + +:(before "End Primitive Recipe Declarations") +HASH, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "hash", HASH); +:(before "End Primitive Recipe Checks") +case HASH: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'hash' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case HASH: { + const reagent& input = current_instruction().ingredients.at(0); + products.resize(1); + products.at(0).push_back(hash(0, input)); + break; +} + +//: in all the code below, the intermediate results of hashing are threaded through 'h' + +:(code) +size_t hash(size_t h, reagent/*copy*/ r) { + canonize(r); + if (is_mu_string(r)) // optimization + return hash_mu_string(h, r); + else if (is_mu_address(r)) + return hash_mu_address(h, r); + else if (is_mu_scalar(r)) + return hash_mu_scalar(h, r); + else if (is_mu_array(r)) + return hash_mu_array(h, r); + else if (is_mu_container(r)) + return hash_mu_container(h, r); + else if (is_mu_exclusive_container(r)) + return hash_mu_exclusive_container(h, r); + assert(false); +} + +size_t hash_mu_scalar(size_t h, const reagent& r) { + double input = is_literal(r) ? r.value : get_or_insert(Memory, r.value); + return hash_iter(h, static_cast(input)); +} + +size_t hash_mu_address(size_t h, reagent& r) { + if (r.value == 0) return 0; + trace(9999, "mem") << "location " << r.value << " is " << no_scientific(get_or_insert(Memory, r.value)) << end(); + r.value = get_or_insert(Memory, r.value); + if (r.value != 0) { + trace(9999, "mem") << "skipping refcount at " << r.value << end(); + r.set_value(r.value+1); // skip refcount + } + drop_from_type(r, "address"); + return hash(h, r); +} + +size_t hash_mu_string(size_t h, const reagent& r) { + string input = read_mu_string(get_or_insert(Memory, r.value)); + for (int i = 0; i < SIZE(input); ++i) { + h = hash_iter(h, static_cast(input.at(i))); +//? cerr << i << ": " << h << '\n'; + } + return h; +} + +size_t hash_mu_array(size_t h, const reagent& r) { + int size = get_or_insert(Memory, r.value); + reagent/*copy*/ elem = r; + delete elem.type; + elem.type = copy_array_element(r.type); + for (int i=0, address = r.value+1; i < size; ++i, address += size_of(elem)) { + reagent/*copy*/ tmp = elem; + tmp.value = address; + h = hash(h, tmp); +//? cerr << i << " (" << address << "): " << h << '\n'; + } + return h; +} + +size_t hash_mu_container(size_t h, const reagent& r) { + assert(r.type->value); + type_info& info = get(Type, r.type->value); + int address = r.value; + int offset = 0; + for (int i = 0; i < SIZE(info.elements); ++i) { + reagent/*copy*/ element = element_type(r.type, i); + if (has_property(element, "ignore-for-hash")) continue; + element.set_value(address+offset); + h = hash(h, element); +//? cerr << i << ": " << h << '\n'; + offset += size_of(info.elements.at(i).type); + } + return h; +} + +size_t hash_mu_exclusive_container(size_t h, const reagent& r) { + assert(r.type->value); + int tag = get(Memory, r.value); + reagent/*copy*/ variant = variant_type(r, tag); + // todo: move this error to container definition time + if (has_property(variant, "ignore-for-hash")) + raise << get(Type, r.type->value).name << ": /ignore-for-hash won't work in exclusive containers\n" << end(); + variant.set_value(r.value + /*skip tag*/1); + h = hash(h, variant); + return h; +} + +size_t hash_iter(size_t h, size_t input) { + h += input; + h += (h<<10); + h ^= (h>>6); + + h += (h<<3); + h ^= (h>>11); + h += (h<<15); + return h; +} + +:(scenario hash_container_checks_all_elements) +container foo [ + x:number + y:character +] +def main [ + 1:foo <- merge 34, 97/a + 3:number <- hash 1:foo + return-unless 3:number + 4:foo <- merge 34, 98/a + 6:number <- hash 4:foo + return-unless 6:number + 7:boolean <- equal 3:number, 6:number +] +# hash on containers includes all elements ++mem: storing 0 in location 7 + +:(scenario hash_exclusive_container_checks_all_elements) +exclusive-container foo [ + x:bar + y:number +] +container bar [ + a:number + b:number +] +def main [ + 1:foo <- merge 0/x, 34, 35 + 4:number <- hash 1:foo + return-unless 4:number + 5:foo <- merge 0/x, 34, 36 + 8:number <- hash 5:foo + return-unless 8:number + 9:boolean <- equal 4:number, 8:number +] +# hash on containers includes all elements ++mem: storing 0 in location 9 + +:(scenario hash_can_ignore_container_elements) +container foo [ + x:number + y:character/ignore-for-hash +] +def main [ + 1:foo <- merge 34, 97/a + 3:number <- hash 1:foo + return-unless 3:number + 4:foo <- merge 34, 98/a + 6:number <- hash 4:foo + return-unless 6:number + 7:boolean <- equal 3:number, 6:number +] +# hashes match even though y is different ++mem: storing 1 in location 7 + +//: These properties aren't necessary for hash, they just test that the +//: current implementation works like we think it does. + +:(scenario hash_of_zero_address) +def main [ + 1:address:number <- copy 0 + 2:number <- hash 1:address:number +] ++mem: storing 0 in location 2 + +//: This is probably too aggressive, but we need some way to avoid depending +//: on the precise bit pattern of a floating-point number. +:(scenario hash_of_numbers_ignores_fractional_part) +def main [ + 1:number <- hash 1.5 + 2:number <- hash 1 + 3:boolean <- equal 1:number, 2:number +] ++mem: storing 1 in location 3 + +:(scenario hash_of_array_same_as_string) +def main [ + 10:number <- copy 3 + 11:number <- copy 97 + 12:number <- copy 98 + 13:number <- copy 99 + 2:number <- hash 10:array:number/unsafe + return-unless 2:number + 3:address:array:character <- new [abc] + 4:number <- hash 3:address:array:character + return-unless 4:number + 5:boolean <- equal 2:number, 4:number +] ++mem: storing 1 in location 5 + +:(scenario hash_ignores_address_value) +def main [ + 1:address:number <- new number:type + *1:address:number <- copy 34 + 2:number <- hash 1:address:number + 3:address:number <- new number:type + *3:address:number <- copy 34 + 4:number <- hash 3:address:number + 5:boolean <- equal 2:number, 4:number +] +# different addresses hash to the same result as long as the values the point to do so ++mem: storing 1 in location 5 + +:(scenario hash_ignores_address_refcount) +def main [ + 1:address:number <- new number:type + *1:address:number <- copy 34 + 2:number <- hash 1:address:number + return-unless 2:number + # increment refcount + 3:address:number <- copy 1:address:number + 4:number <- hash 3:address:number + return-unless 4:number + 5:boolean <- equal 2:number, 4:number +] +# hash doesn't change when refcount changes ++mem: storing 1 in location 5 + +:(scenario hash_container_depends_only_on_elements) +container foo [ + x:number + y:character +] +container bar [ + x:number + y:character +] +def main [ + 1:foo <- merge 34, 97/a + 3:number <- hash 1:foo + return-unless 3:number + 4:bar <- merge 34, 97/a + 6:number <- hash 4:bar + return-unless 6:number + 7:boolean <- equal 3:number, 6:number +] +# containers with identical elements return identical hashes ++mem: storing 1 in location 7 + +:(scenario hash_container_depends_only_on_elements_2) +container foo [ + x:number + y:character + z:address:number +] +def main [ + 1:address:number <- new number:type + *1:address:number <- copy 34 + 2:foo <- merge 34, 97/a, 1:address:number + 5:number <- hash 2:foo + return-unless 5:number + 6:address:number <- new number:type + *6:address:number <- copy 34 + 7:foo <- merge 34, 97/a, 6:address:number + 10:number <- hash 7:foo + return-unless 10:number + 11:boolean <- equal 5:number, 10:number +] +# containers with identical 'leaf' elements return identical hashes ++mem: storing 1 in location 11 + +:(scenario hash_container_depends_only_on_elements_3) +container foo [ + x:number + y:character + z:bar +] +container bar [ + x:number + y:number +] +def main [ + 1:foo <- merge 34, 97/a, 47, 48 + 6:number <- hash 1:foo + return-unless 6:number + 7:foo <- merge 34, 97/a, 47, 48 + 12:number <- hash 7:foo + return-unless 12:number + 13:boolean <- equal 6:number, 12:number +] +# containers with identical 'leaf' elements return identical hashes ++mem: storing 1 in location 13 + +:(scenario hash_exclusive_container_ignores_tag) +exclusive-container foo [ + x:bar + y:number +] +container bar [ + a:number + b:number +] +def main [ + 1:foo <- merge 0/x, 34, 35 + 4:number <- hash 1:foo + return-unless 4:number + 5:bar <- merge 34, 35 + 7:number <- hash 5:bar + return-unless 7:number + 8:boolean <- equal 4:number, 7:number +] +# hash on containers includes all elements ++mem: storing 1 in location 8 + +//: An older version that supported only strings. +//: Hash functions are subtle and easy to get wrong, so we keep the old +//: version around and check that the new one is consistent with it. + +:(scenario hash_matches_old_version) +def main [ + 1:address:array:character <- new [abc] + 2:number <- hash 1:address:array:character + 3:number <- hash_old 1:address:array:character + 4:boolean <- equal 2:number, 3:number +] ++mem: storing 1 in location 4 + +:(before "End Primitive Recipe Declarations") +HASH_OLD, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "hash_old", HASH_OLD); +:(before "End Primitive Recipe Checks") +case HASH_OLD: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'hash_old' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_string(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "'hash_old' currently only supports strings (address:array:character), but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case HASH_OLD: { + string input = read_mu_string(ingredients.at(0).at(0)); + size_t h = 0 ; + + for (int i = 0; i < SIZE(input); ++i) { + h += static_cast(input.at(i)); + h += (h<<10); + h ^= (h>>6); + + h += (h<<3); + h ^= (h>>11); + h += (h<<15); + } + + products.resize(1); + products.at(0).push_back(h); + break; +} diff --git a/069table.mu b/069table.mu deleted file mode 100644 index 4c98cf91..00000000 --- a/069table.mu +++ /dev/null @@ -1,87 +0,0 @@ -# A table is like an array, except that its keys are not integers but -# arbitrary types. - -scenario table-read-write [ - run [ - local-scope - tab:address:table:number:number <- new-table 30 - put-index tab, 12, 34 - 1:number/raw <- index tab, 12 - ] - memory-should-contain [ - 1 <- 34 - ] -] - -scenario table-read-write-non-integer [ - run [ - local-scope - key:address:array:character <- new [abc def] - {tab: (address table (address array character) number)} <- new-table 30 - put-index tab, key, 34 - 1:number/raw <- index tab, key - ] - memory-should-contain [ - 1 <- 34 - ] -] - -container table:_key:_value [ - length:number - capacity:number - data:address:array:table_row:_key:_value -] - -container table_row:_key:_value [ - occupied?:boolean - key:_key - value:_value -] - -def new-table capacity:number -> result:address:table:_key:_value [ - local-scope - load-ingredients - result <- new {(table _key _value): type} - data:address:array:table_row:_key:_value <- new {(table_row _key _value): type}, capacity - *result <- merge 0/length, capacity, data -] - -def put-index table:address:table:_key:_value, key:_key, value:_value -> table:address:table:_key:_value [ - local-scope - load-ingredients - hash:number <- hash key - hash <- abs hash - capacity:number <- get *table, capacity:offset - _, hash <- divide-with-remainder hash, capacity - hash <- abs hash # in case hash overflows into a negative integer - table-data:address:array:table_row:_key:_value <- get *table, data:offset - x:table_row:_key:_value <- index *table-data, hash - occupied?:boolean <- get x, occupied?:offset - not-occupied?:boolean <- not occupied?:boolean - assert not-occupied?, [can't handle collisions yet] - new-row:table_row:_key:_value <- merge 1/true, key, value - *table-data <- put-index *table-data, hash, new-row -] - -def abs n:number -> result:number [ - local-scope - load-ingredients - positive?:boolean <- greater-or-equal n, 0 - return-if positive?, n - result <- multiply n, -1 -] - -def index table:address:table:_key:_value, key:_key -> result:_value [ - local-scope - load-ingredients - hash:number <- hash key - hash <- abs hash - capacity:number <- get *table, capacity:offset - _, hash <- divide-with-remainder hash, capacity - hash <- abs hash # in case hash overflows into a negative integer - table-data:address:array:table_row:_key:_value <- get *table, data:offset - x:table_row:_key:_value <- index *table-data, hash - occupied?:boolean <- get x, occupied?:offset - assert occupied?, [can't handle missing elements yet] - result <- get x, value:offset -] diff --git a/070recipe.cc b/070recipe.cc deleted file mode 100644 index e41eb494..00000000 --- a/070recipe.cc +++ /dev/null @@ -1,249 +0,0 @@ -//: So far we've been calling a fixed recipe in each instruction, but we'd -//: also like to make the recipe a variable, pass recipes to "higher-order" -//: recipes, return recipes from recipes and so on. -//: -//: todo: support storing shape-shifting recipes into recipe variables and calling them - -:(scenario call_literal_recipe) -def main [ - 1:number <- call f, 34 -] -def f x:number -> y:number [ - local-scope - load-ingredients - y <- copy x -] -+mem: storing 34 in location 1 - -:(scenario call_variable) -def main [ - {1: (recipe number -> number)} <- copy f - 2:number <- call {1: (recipe number -> number)}, 34 -] -def f x:number -> y:number [ - local-scope - load-ingredients - y <- copy x -] -+mem: storing 34 in location 2 - -:(before "End Mu Types Initialization") -put(Type_ordinal, "recipe-literal", 0); -// 'recipe' variables can store recipe-literal -type_ordinal recipe = put(Type_ordinal, "recipe", Next_type_ordinal++); -get_or_insert(Type, recipe).name = "recipe"; - -:(before "End Null-type is_disqualified Exceptions") -if (!x.type && contains_key(Recipe_ordinal, x.name)) { - x.type = new type_tree("recipe-literal"); - x.set_value(get(Recipe_ordinal, x.name)); - return true; -} - -:(before "End Primitive Recipe Declarations") -CALL, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "call", CALL); -:(before "End Primitive Recipe Checks") -case CALL: { - if (inst.ingredients.empty()) { - raise << maybe(get(Recipe, r).name) << "'call' requires at least one ingredient (the recipe to call)\n" << end(); - break; - } - if (!is_mu_recipe(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'call' should be a recipe, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case CALL: { - // Begin Call - if (Trace_stream) { - ++Trace_stream->callstack_depth; - trace("trace") << "indirect 'call': incrementing callstack depth to " << Trace_stream->callstack_depth << end(); - assert(Trace_stream->callstack_depth < 9000); // 9998-101 plus cushion - } - if (!ingredients.at(0).at(0)) { - raise << maybe(current_recipe_name()) << "tried to call empty recipe in '" << to_string(current_instruction()) << "'" << end(); - break; - } - const instruction& caller_instruction = current_instruction(); - Current_routine->calls.push_front(call(ingredients.at(0).at(0))); - ingredients.erase(ingredients.begin()); // drop the callee - finish_call_housekeeping(caller_instruction, ingredients); - continue; -} - -//:: check types for 'call' instructions - -:(scenario call_check_literal_recipe) -% Hide_errors = true; -def main [ - 1:number <- call f, 34 -] -def f x:point -> y:point [ - local-scope - load-ingredients - y <- copy x -] -+error: main: ingredient 0 has the wrong type at '1:number <- call f, 34' -+error: main: product 0 has the wrong type at '1:number <- call f, 34' - -:(scenario call_check_variable_recipe) -% Hide_errors = true; -def main [ - {1: (recipe point -> point)} <- copy f - 2:number <- call {1: (recipe point -> point)}, 34 -] -def f x:point -> y:point [ - local-scope - load-ingredients - y <- copy x -] -+error: main: ingredient 0 has the wrong type at '2:number <- call {1: (recipe point -> point)}, 34' -+error: main: product 0 has the wrong type at '2:number <- call {1: (recipe point -> point)}, 34' - -:(after "Transform.push_back(check_instruction)") -Transform.push_back(check_indirect_calls_against_header); // idempotent -:(code) -void check_indirect_calls_against_header(const recipe_ordinal r) { - trace(9991, "transform") << "--- type-check 'call' instructions inside recipe " << get(Recipe, r).name << end(); - const recipe& caller = get(Recipe, r); - for (int i = 0; i < SIZE(caller.steps); ++i) { - const instruction& inst = caller.steps.at(i); - if (inst.operation != CALL) continue; - if (inst.ingredients.empty()) continue; // error raised above - const reagent& callee = inst.ingredients.at(0); - if (!is_mu_recipe(callee)) continue; // error raised above - const recipe callee_header = is_literal(callee) ? get(Recipe, callee.value) : from_reagent(inst.ingredients.at(0)); - if (!callee_header.has_header) continue; - for (long int i = /*skip callee*/1; i < min(SIZE(inst.ingredients), SIZE(callee_header.ingredients)+/*skip callee*/1); ++i) { - if (!types_coercible(callee_header.ingredients.at(i-/*skip callee*/1), inst.ingredients.at(i))) - raise << maybe(caller.name) << "ingredient " << i-/*skip callee*/1 << " has the wrong type at '" << inst.original_string << "'\n" << end(); - } - for (long int i = 0; i < min(SIZE(inst.products), SIZE(callee_header.products)); ++i) { - if (is_dummy(inst.products.at(i))) continue; - if (!types_coercible(callee_header.products.at(i), inst.products.at(i))) - raise << maybe(caller.name) << "product " << i << " has the wrong type at '" << inst.original_string << "'\n" << end(); - } - } -} - -recipe from_reagent(const reagent& r) { - assert(r.type->name == "recipe"); - recipe result_header; // will contain only ingredients and products, nothing else - result_header.has_header = true; - const type_tree* curr = r.type->right; - for (; curr; curr=curr->right) { - if (curr->name == "->") { - curr = curr->right; // skip delimiter - break; - } - result_header.ingredients.push_back(next_recipe_reagent(curr)); - } - for (; curr; curr=curr->right) - result_header.products.push_back(next_recipe_reagent(curr)); - return result_header; -} - -reagent next_recipe_reagent(const type_tree* curr) { - if (!curr->left) return reagent("recipe:"+curr->name); - reagent result; - result.name = "recipe"; - result.type = new type_tree(*curr->left); - return result; -} - -bool is_mu_recipe(const reagent& r) { - if (!r.type) return false; - if (r.type->name == "recipe") return true; - if (r.type->name == "recipe-literal") return true; - // End is_mu_recipe Cases - return false; -} - -:(scenario copy_typecheck_recipe_variable) -% Hide_errors = true; -def main [ - 3:number <- copy 34 # abc def - {1: (recipe number -> number)} <- copy f # store literal in a matching variable - {2: (recipe boolean -> boolean)} <- copy {1: (recipe number -> number)} # mismatch between recipe variables -] -def f x:number -> y:number [ - local-scope - load-ingredients - y <- copy x -] -+error: main: can't copy '{1: (recipe number -> number)}' to '{2: (recipe boolean -> boolean)}'; types don't match - -:(scenario copy_typecheck_recipe_variable_2) -% Hide_errors = true; -def main [ - {1: (recipe number -> number)} <- copy f # mismatch with a recipe literal -] -def f x:boolean -> y:boolean [ - local-scope - load-ingredients - y <- copy x -] -+error: main: can't copy 'f' to '{1: (recipe number -> number)}'; types don't match - -:(before "End Matching Types For Literal(to)") -if (is_mu_recipe(to)) { - if (!contains_key(Recipe, from.value)) { - raise << "trying to store recipe " << from.name << " into " << to_string(to) << " but there's no such recipe\n" << end(); - return false; - } - const recipe& rrhs = get(Recipe, from.value); - const recipe& rlhs = from_reagent(to); - for (long int i = 0; i < min(SIZE(rlhs.ingredients), SIZE(rrhs.ingredients)); ++i) { - if (!types_match(rlhs.ingredients.at(i), rrhs.ingredients.at(i))) - return false; - } - for (long int i = 0; i < min(SIZE(rlhs.products), SIZE(rrhs.products)); ++i) { - if (!types_match(rlhs.products.at(i), rrhs.products.at(i))) - return false; - } - return true; -} - -:(scenario call_variable_compound_ingredient) -def main [ - {1: (recipe (address number) -> number)} <- copy f - 2:address:number <- copy 0 - 3:number <- call {1: (recipe (address number) -> number)}, 2:address:number -] -def f x:address:number -> y:number [ - local-scope - load-ingredients - y <- copy x -] -$error: 0 - -//: make sure we don't accidentally break on a function literal -:(scenario jump_forbidden_on_recipe_literals) -% Hide_errors = true; -def foo [ - local-scope -] -def main [ - local-scope - { - break-if foo - } -] -# error should be as if foo is not a recipe -+error: main: missing type for foo in 'break-if foo' - -:(before "End JUMP_IF Checks") -check_for_recipe_literals(inst, get(Recipe, r)); -:(before "End JUMP_UNLESS Checks") -check_for_recipe_literals(inst, get(Recipe, r)); -:(code) -void check_for_recipe_literals(const instruction& inst, const recipe& caller) { - for (int i = 0; i < SIZE(inst.ingredients); ++i) { - if (is_mu_recipe(inst.ingredients.at(i))) - raise << maybe(caller.name) << "missing type for " << inst.ingredients.at(i).original_string << " in '" << inst.original_string << "'\n" << end(); - } -} diff --git a/070table.mu b/070table.mu new file mode 100644 index 00000000..4c98cf91 --- /dev/null +++ b/070table.mu @@ -0,0 +1,87 @@ +# A table is like an array, except that its keys are not integers but +# arbitrary types. + +scenario table-read-write [ + run [ + local-scope + tab:address:table:number:number <- new-table 30 + put-index tab, 12, 34 + 1:number/raw <- index tab, 12 + ] + memory-should-contain [ + 1 <- 34 + ] +] + +scenario table-read-write-non-integer [ + run [ + local-scope + key:address:array:character <- new [abc def] + {tab: (address table (address array character) number)} <- new-table 30 + put-index tab, key, 34 + 1:number/raw <- index tab, key + ] + memory-should-contain [ + 1 <- 34 + ] +] + +container table:_key:_value [ + length:number + capacity:number + data:address:array:table_row:_key:_value +] + +container table_row:_key:_value [ + occupied?:boolean + key:_key + value:_value +] + +def new-table capacity:number -> result:address:table:_key:_value [ + local-scope + load-ingredients + result <- new {(table _key _value): type} + data:address:array:table_row:_key:_value <- new {(table_row _key _value): type}, capacity + *result <- merge 0/length, capacity, data +] + +def put-index table:address:table:_key:_value, key:_key, value:_value -> table:address:table:_key:_value [ + local-scope + load-ingredients + hash:number <- hash key + hash <- abs hash + capacity:number <- get *table, capacity:offset + _, hash <- divide-with-remainder hash, capacity + hash <- abs hash # in case hash overflows into a negative integer + table-data:address:array:table_row:_key:_value <- get *table, data:offset + x:table_row:_key:_value <- index *table-data, hash + occupied?:boolean <- get x, occupied?:offset + not-occupied?:boolean <- not occupied?:boolean + assert not-occupied?, [can't handle collisions yet] + new-row:table_row:_key:_value <- merge 1/true, key, value + *table-data <- put-index *table-data, hash, new-row +] + +def abs n:number -> result:number [ + local-scope + load-ingredients + positive?:boolean <- greater-or-equal n, 0 + return-if positive?, n + result <- multiply n, -1 +] + +def index table:address:table:_key:_value, key:_key -> result:_value [ + local-scope + load-ingredients + hash:number <- hash key + hash <- abs hash + capacity:number <- get *table, capacity:offset + _, hash <- divide-with-remainder hash, capacity + hash <- abs hash # in case hash overflows into a negative integer + table-data:address:array:table_row:_key:_value <- get *table, data:offset + x:table_row:_key:_value <- index *table-data, hash + occupied?:boolean <- get x, occupied?:offset + assert occupied?, [can't handle missing elements yet] + result <- get x, value:offset +] diff --git a/071recipe.cc b/071recipe.cc new file mode 100644 index 00000000..e41eb494 --- /dev/null +++ b/071recipe.cc @@ -0,0 +1,249 @@ +//: So far we've been calling a fixed recipe in each instruction, but we'd +//: also like to make the recipe a variable, pass recipes to "higher-order" +//: recipes, return recipes from recipes and so on. +//: +//: todo: support storing shape-shifting recipes into recipe variables and calling them + +:(scenario call_literal_recipe) +def main [ + 1:number <- call f, 34 +] +def f x:number -> y:number [ + local-scope + load-ingredients + y <- copy x +] ++mem: storing 34 in location 1 + +:(scenario call_variable) +def main [ + {1: (recipe number -> number)} <- copy f + 2:number <- call {1: (recipe number -> number)}, 34 +] +def f x:number -> y:number [ + local-scope + load-ingredients + y <- copy x +] ++mem: storing 34 in location 2 + +:(before "End Mu Types Initialization") +put(Type_ordinal, "recipe-literal", 0); +// 'recipe' variables can store recipe-literal +type_ordinal recipe = put(Type_ordinal, "recipe", Next_type_ordinal++); +get_or_insert(Type, recipe).name = "recipe"; + +:(before "End Null-type is_disqualified Exceptions") +if (!x.type && contains_key(Recipe_ordinal, x.name)) { + x.type = new type_tree("recipe-literal"); + x.set_value(get(Recipe_ordinal, x.name)); + return true; +} + +:(before "End Primitive Recipe Declarations") +CALL, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "call", CALL); +:(before "End Primitive Recipe Checks") +case CALL: { + if (inst.ingredients.empty()) { + raise << maybe(get(Recipe, r).name) << "'call' requires at least one ingredient (the recipe to call)\n" << end(); + break; + } + if (!is_mu_recipe(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'call' should be a recipe, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case CALL: { + // Begin Call + if (Trace_stream) { + ++Trace_stream->callstack_depth; + trace("trace") << "indirect 'call': incrementing callstack depth to " << Trace_stream->callstack_depth << end(); + assert(Trace_stream->callstack_depth < 9000); // 9998-101 plus cushion + } + if (!ingredients.at(0).at(0)) { + raise << maybe(current_recipe_name()) << "tried to call empty recipe in '" << to_string(current_instruction()) << "'" << end(); + break; + } + const instruction& caller_instruction = current_instruction(); + Current_routine->calls.push_front(call(ingredients.at(0).at(0))); + ingredients.erase(ingredients.begin()); // drop the callee + finish_call_housekeeping(caller_instruction, ingredients); + continue; +} + +//:: check types for 'call' instructions + +:(scenario call_check_literal_recipe) +% Hide_errors = true; +def main [ + 1:number <- call f, 34 +] +def f x:point -> y:point [ + local-scope + load-ingredients + y <- copy x +] ++error: main: ingredient 0 has the wrong type at '1:number <- call f, 34' ++error: main: product 0 has the wrong type at '1:number <- call f, 34' + +:(scenario call_check_variable_recipe) +% Hide_errors = true; +def main [ + {1: (recipe point -> point)} <- copy f + 2:number <- call {1: (recipe point -> point)}, 34 +] +def f x:point -> y:point [ + local-scope + load-ingredients + y <- copy x +] ++error: main: ingredient 0 has the wrong type at '2:number <- call {1: (recipe point -> point)}, 34' ++error: main: product 0 has the wrong type at '2:number <- call {1: (recipe point -> point)}, 34' + +:(after "Transform.push_back(check_instruction)") +Transform.push_back(check_indirect_calls_against_header); // idempotent +:(code) +void check_indirect_calls_against_header(const recipe_ordinal r) { + trace(9991, "transform") << "--- type-check 'call' instructions inside recipe " << get(Recipe, r).name << end(); + const recipe& caller = get(Recipe, r); + for (int i = 0; i < SIZE(caller.steps); ++i) { + const instruction& inst = caller.steps.at(i); + if (inst.operation != CALL) continue; + if (inst.ingredients.empty()) continue; // error raised above + const reagent& callee = inst.ingredients.at(0); + if (!is_mu_recipe(callee)) continue; // error raised above + const recipe callee_header = is_literal(callee) ? get(Recipe, callee.value) : from_reagent(inst.ingredients.at(0)); + if (!callee_header.has_header) continue; + for (long int i = /*skip callee*/1; i < min(SIZE(inst.ingredients), SIZE(callee_header.ingredients)+/*skip callee*/1); ++i) { + if (!types_coercible(callee_header.ingredients.at(i-/*skip callee*/1), inst.ingredients.at(i))) + raise << maybe(caller.name) << "ingredient " << i-/*skip callee*/1 << " has the wrong type at '" << inst.original_string << "'\n" << end(); + } + for (long int i = 0; i < min(SIZE(inst.products), SIZE(callee_header.products)); ++i) { + if (is_dummy(inst.products.at(i))) continue; + if (!types_coercible(callee_header.products.at(i), inst.products.at(i))) + raise << maybe(caller.name) << "product " << i << " has the wrong type at '" << inst.original_string << "'\n" << end(); + } + } +} + +recipe from_reagent(const reagent& r) { + assert(r.type->name == "recipe"); + recipe result_header; // will contain only ingredients and products, nothing else + result_header.has_header = true; + const type_tree* curr = r.type->right; + for (; curr; curr=curr->right) { + if (curr->name == "->") { + curr = curr->right; // skip delimiter + break; + } + result_header.ingredients.push_back(next_recipe_reagent(curr)); + } + for (; curr; curr=curr->right) + result_header.products.push_back(next_recipe_reagent(curr)); + return result_header; +} + +reagent next_recipe_reagent(const type_tree* curr) { + if (!curr->left) return reagent("recipe:"+curr->name); + reagent result; + result.name = "recipe"; + result.type = new type_tree(*curr->left); + return result; +} + +bool is_mu_recipe(const reagent& r) { + if (!r.type) return false; + if (r.type->name == "recipe") return true; + if (r.type->name == "recipe-literal") return true; + // End is_mu_recipe Cases + return false; +} + +:(scenario copy_typecheck_recipe_variable) +% Hide_errors = true; +def main [ + 3:number <- copy 34 # abc def + {1: (recipe number -> number)} <- copy f # store literal in a matching variable + {2: (recipe boolean -> boolean)} <- copy {1: (recipe number -> number)} # mismatch between recipe variables +] +def f x:number -> y:number [ + local-scope + load-ingredients + y <- copy x +] ++error: main: can't copy '{1: (recipe number -> number)}' to '{2: (recipe boolean -> boolean)}'; types don't match + +:(scenario copy_typecheck_recipe_variable_2) +% Hide_errors = true; +def main [ + {1: (recipe number -> number)} <- copy f # mismatch with a recipe literal +] +def f x:boolean -> y:boolean [ + local-scope + load-ingredients + y <- copy x +] ++error: main: can't copy 'f' to '{1: (recipe number -> number)}'; types don't match + +:(before "End Matching Types For Literal(to)") +if (is_mu_recipe(to)) { + if (!contains_key(Recipe, from.value)) { + raise << "trying to store recipe " << from.name << " into " << to_string(to) << " but there's no such recipe\n" << end(); + return false; + } + const recipe& rrhs = get(Recipe, from.value); + const recipe& rlhs = from_reagent(to); + for (long int i = 0; i < min(SIZE(rlhs.ingredients), SIZE(rrhs.ingredients)); ++i) { + if (!types_match(rlhs.ingredients.at(i), rrhs.ingredients.at(i))) + return false; + } + for (long int i = 0; i < min(SIZE(rlhs.products), SIZE(rrhs.products)); ++i) { + if (!types_match(rlhs.products.at(i), rrhs.products.at(i))) + return false; + } + return true; +} + +:(scenario call_variable_compound_ingredient) +def main [ + {1: (recipe (address number) -> number)} <- copy f + 2:address:number <- copy 0 + 3:number <- call {1: (recipe (address number) -> number)}, 2:address:number +] +def f x:address:number -> y:number [ + local-scope + load-ingredients + y <- copy x +] +$error: 0 + +//: make sure we don't accidentally break on a function literal +:(scenario jump_forbidden_on_recipe_literals) +% Hide_errors = true; +def foo [ + local-scope +] +def main [ + local-scope + { + break-if foo + } +] +# error should be as if foo is not a recipe ++error: main: missing type for foo in 'break-if foo' + +:(before "End JUMP_IF Checks") +check_for_recipe_literals(inst, get(Recipe, r)); +:(before "End JUMP_UNLESS Checks") +check_for_recipe_literals(inst, get(Recipe, r)); +:(code) +void check_for_recipe_literals(const instruction& inst, const recipe& caller) { + for (int i = 0; i < SIZE(inst.ingredients); ++i) { + if (is_mu_recipe(inst.ingredients.at(i))) + raise << maybe(caller.name) << "missing type for " << inst.ingredients.at(i).original_string << " in '" << inst.original_string << "'\n" << end(); + } +} diff --git a/071scheduler.cc b/071scheduler.cc deleted file mode 100644 index 99d5488b..00000000 --- a/071scheduler.cc +++ /dev/null @@ -1,625 +0,0 @@ -//: Run a second routine concurrently using 'start-running', without any -//: guarantees on how the operations in each are interleaved with each other. - -:(scenario scheduler) -def f1 [ - start-running f2 - # wait for f2 to run - { - jump-unless 1:number, -1 - } -] -def f2 [ - 1:number <- copy 1 -] -+schedule: f1 -+schedule: f2 - -//: first, add a deadline to run(routine) -//: these changes are ugly and brittle; just close your nose and get through the next few lines -:(replace "void run_current_routine()") -void run_current_routine(int time_slice) -:(replace "while (!Current_routine->completed())" following "void run_current_routine(int time_slice)") -int ninstrs = 0; -while (Current_routine->state == RUNNING && ninstrs < time_slice) -:(after "Running One Instruction") -ninstrs++; - -//: now the rest of the scheduler is clean - -:(before "struct routine") -enum routine_state { - RUNNING, - COMPLETED, - // End routine States -}; -:(before "End routine Fields") -enum routine_state state; -:(before "End routine Constructor") -state = RUNNING; - -:(before "End Globals") -vector Routines; -int Current_routine_index = 0; -int Scheduling_interval = 500; -:(before "End Setup") -Scheduling_interval = 500; -Routines.clear(); -:(replace{} "void run(recipe_ordinal r)") -void run(recipe_ordinal r) { - run(new routine(r)); -} - -:(code) -void run(routine* rr) { - Routines.push_back(rr); - Current_routine_index = 0, Current_routine = Routines.at(0); - while (!all_routines_done()) { - skip_to_next_routine(); - assert(Current_routine); - assert(Current_routine->state == RUNNING); - trace(9990, "schedule") << current_routine_label() << end(); - run_current_routine(Scheduling_interval); - // Scheduler State Transitions - if (Current_routine->completed()) - Current_routine->state = COMPLETED; - // End Scheduler State Transitions - - // Scheduler Cleanup - // End Scheduler Cleanup - } -} - -bool all_routines_done() { - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->state == RUNNING) - return false; - } - return true; -} - -// skip Current_routine_index past non-RUNNING routines -void skip_to_next_routine() { - assert(!Routines.empty()); - assert(Current_routine_index < SIZE(Routines)); - for (int i = (Current_routine_index+1)%SIZE(Routines); i != Current_routine_index; i = (i+1)%SIZE(Routines)) { - if (Routines.at(i)->state == RUNNING) { - Current_routine_index = i; - Current_routine = Routines.at(i); - return; - } - } -} - -string current_routine_label() { - ostringstream result; - const call_stack& calls = Current_routine->calls; - for (call_stack::const_iterator p = calls.begin(); p != calls.end(); ++p) { - if (p != calls.begin()) result << '/'; - result << get(Recipe, p->running_recipe).name; - } - return result.str(); -} - -:(before "End Teardown") -for (int i = 0; i < SIZE(Routines); ++i) - delete Routines.at(i); -Routines.clear(); -Current_routine = NULL; - -//: special case for the very first routine -:(replace{} "void run_main(int argc, char* argv[])") -void run_main(int argc, char* argv[]) { - recipe_ordinal r = get(Recipe_ordinal, "main"); - assert(r); - routine* main_routine = new routine(r); - // pass in commandline args as ingredients to main - // todo: test this - Current_routine = main_routine; - for (int i = 1; i < argc; ++i) { - vector arg; - arg.push_back(new_mu_string(argv[i])); - current_call().ingredient_atoms.push_back(arg); - } - run(main_routine); -} - -//:: To schedule new routines to run, call 'start-running'. - -//: 'start-running' will return a unique id for the routine that was created. -//: routine id is a number, but don't do any arithmetic on it -:(before "End routine Fields") -int id; -:(before "End Globals") -int Next_routine_id = 1; -:(before "End Setup") -Next_routine_id = 1; -:(before "End routine Constructor") -id = Next_routine_id; -Next_routine_id++; - -//: routines save the routine that spawned them -:(before "End routine Fields") -// todo: really should be routine_id, but that's less efficient. -int parent_index; // only < 0 if there's no parent_index -:(before "End routine Constructor") -parent_index = -1; - -:(before "End Primitive Recipe Declarations") -START_RUNNING, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "start-running", START_RUNNING); -:(before "End Primitive Recipe Checks") -case START_RUNNING: { - if (inst.ingredients.empty()) { - raise << maybe(get(Recipe, r).name) << "'start-running' requires at least one ingredient: the recipe to start running\n" << end(); - break; - } - if (!is_mu_recipe(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'start-running' should be a recipe, but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case START_RUNNING: { - routine* new_routine = new routine(ingredients.at(0).at(0)); - new_routine->parent_index = Current_routine_index; - // populate ingredients - for (int i = 1; i < SIZE(current_instruction().ingredients); ++i) { - new_routine->calls.front().ingredient_atoms.push_back(ingredients.at(i)); - reagent/*copy*/ ingredient = current_instruction().ingredients.at(i); - canonize_type(ingredient); - new_routine->calls.front().ingredients.push_back(ingredient); - } - Routines.push_back(new_routine); - products.resize(1); - products.at(0).push_back(new_routine->id); - break; -} - -:(scenario scheduler_runs_single_routine) -% Scheduling_interval = 1; -def f1 [ - 1:number <- copy 0 - 2:number <- copy 0 -] -+schedule: f1 -+run: {1: "number"} <- copy {0: "literal"} -+schedule: f1 -+run: {2: "number"} <- copy {0: "literal"} - -:(scenario scheduler_interleaves_routines) -% Scheduling_interval = 1; -def f1 [ - start-running f2 - 1:number <- copy 0 - 2:number <- copy 0 -] -def f2 [ - 3:number <- copy 0 - 4:number <- copy 0 -] -+schedule: f1 -+run: start-running {f2: "recipe-literal"} -+schedule: f2 -+run: {3: "number"} <- copy {0: "literal"} -+schedule: f1 -+run: {1: "number"} <- copy {0: "literal"} -+schedule: f2 -+run: {4: "number"} <- copy {0: "literal"} -+schedule: f1 -+run: {2: "number"} <- copy {0: "literal"} - -:(scenario start_running_takes_ingredients) -def f1 [ - start-running f2, 3 - # wait for f2 to run - { - jump-unless 1:number, -1 - } -] -def f2 [ - 1:number <- next-ingredient - 2:number <- add 1:number, 1 -] -+mem: storing 4 in location 2 - -:(scenario start_running_returns_routine_id) -def f1 [ - 1:number <- start-running f2 -] -def f2 [ - 12:number <- copy 44 -] -+mem: storing 2 in location 1 - -//: this scenario will require some careful setup in escaped C++ -//: (straining our tangle capabilities to near-breaking point) -:(scenario scheduler_skips_completed_routines) -% recipe_ordinal f1 = load("recipe f1 [\n1:number <- copy 0\n]\n").front(); -% recipe_ordinal f2 = load("recipe f2 [\n2:number <- copy 0\n]\n").front(); -% Routines.push_back(new routine(f1)); // f1 meant to run -% Routines.push_back(new routine(f2)); -% Routines.back()->state = COMPLETED; // f2 not meant to run -# must have at least one routine without escaping -def f3 [ - 3:number <- copy 0 -] -# by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order -+schedule: f1 -+mem: storing 0 in location 1 --schedule: f2 --mem: storing 0 in location 2 -+schedule: f3 -+mem: storing 0 in location 3 - -:(scenario scheduler_starts_at_middle_of_routines) -% Routines.push_back(new routine(COPY)); -% Routines.back()->state = COMPLETED; -def f1 [ - 1:number <- copy 0 - 2:number <- copy 0 -] -+schedule: f1 --run: idle - -//:: Errors in a routine cause it to terminate. - -:(scenario scheduler_terminates_routines_after_errors) -% Hide_errors = true; -% Scheduling_interval = 2; -def f1 [ - start-running f2 - 1:number <- copy 0 - 2:number <- copy 0 -] -def f2 [ - # divide by 0 twice - 3:number <- divide-with-remainder 4, 0 - 4:number <- divide-with-remainder 4, 0 -] -# f2 should stop after first divide by 0 -+error: f2: divide by zero in '3:number <- divide-with-remainder 4, 0' --error: f2: divide by zero in '4:number <- divide-with-remainder 4, 0' - -:(after "operator<<(ostream& os, unused end)") - if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) { - Current_routine->state = COMPLETED; - } - -//:: Routines are marked completed when their parent completes. - -:(scenario scheduler_kills_orphans) -def main [ - start-running f1 - # f1 never actually runs because its parent completes without waiting for it -] -def f1 [ - 1:number <- copy 0 -] --schedule: f1 - -:(before "End Scheduler Cleanup") -for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->state == COMPLETED) continue; - if (Routines.at(i)->parent_index < 0) continue; // root thread - if (has_completed_parent(i)) { - Routines.at(i)->state = COMPLETED; - } -} - -:(code) -bool has_completed_parent(int routine_index) { - for (int j = routine_index; j >= 0; j = Routines.at(j)->parent_index) { - if (Routines.at(j)->state == COMPLETED) - return true; - } - return false; -} - -//:: 'routine-state' can tell if a given routine id is running - -:(scenario routine_state_test) -% Scheduling_interval = 2; -def f1 [ - 1:number/child-id <- start-running f2 - 12:number <- copy 0 # race condition since we don't care about location 12 - # thanks to Scheduling_interval, f2's one instruction runs in between here and completes - 2:number/state <- routine-state 1:number/child-id -] -def f2 [ - 12:number <- copy 0 - # trying to run a second instruction marks routine as completed -] -# recipe f2 should be in state COMPLETED -+mem: storing 1 in location 2 - -:(before "End Primitive Recipe Declarations") -ROUTINE_STATE, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "routine-state", ROUTINE_STATE); -:(before "End Primitive Recipe Checks") -case ROUTINE_STATE: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'routine-state' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case ROUTINE_STATE: { - int id = ingredients.at(0).at(0); - int result = -1; - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->id == id) { - result = Routines.at(i)->state; - break; - } - } - products.resize(1); - products.at(0).push_back(result); - break; -} - -//:: miscellaneous helpers - -:(before "End Primitive Recipe Declarations") -RESTART, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "restart", RESTART); -:(before "End Primitive Recipe Checks") -case RESTART: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'restart' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case RESTART: { - int id = ingredients.at(0).at(0); - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->id == id) { - Routines.at(i)->state = RUNNING; - break; - } - } - break; -} - -:(before "End Primitive Recipe Declarations") -STOP, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "stop", STOP); -:(before "End Primitive Recipe Checks") -case STOP: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'stop' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case STOP: { - int id = ingredients.at(0).at(0); - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->id == id) { - Routines.at(i)->state = COMPLETED; - break; - } - } - break; -} - -:(before "End Primitive Recipe Declarations") -_DUMP_ROUTINES, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES); -:(before "End Primitive Recipe Checks") -case _DUMP_ROUTINES: { - break; -} -:(before "End Primitive Recipe Implementations") -case _DUMP_ROUTINES: { - for (int i = 0; i < SIZE(Routines); ++i) { - cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n'; - } - break; -} - -//: support for stopping routines after some number of cycles - -:(scenario routine_discontinues_past_limit) -% Scheduling_interval = 2; -def f1 [ - 1:number/child-id <- start-running f2 - limit-time 1:number/child-id, 10 - # padding loop just to make sure f2 has time to completed - 2:number <- copy 20 - 2:number <- subtract 2:number, 1 - jump-if 2:number, -2:offset -] -def f2 [ - jump -1:offset # run forever - $print [should never get here], 10/newline -] -# f2 terminates -+schedule: discontinuing routine 2 - -:(before "End routine States") -DISCONTINUED, -:(before "End Scheduler State Transitions") -if (Current_routine->limit >= 0) { - if (Current_routine->limit <= Scheduling_interval) { - trace(9999, "schedule") << "discontinuing routine " << Current_routine->id << end(); - Current_routine->state = DISCONTINUED; - Current_routine->limit = 0; - } - else { - Current_routine->limit -= Scheduling_interval; - } -} - -:(before "End Test Teardown") -if (Passed && any_routines_with_error()) { - Passed = false; - raise << "some routines died with errors\n" << end(); -} -:(before "End Mu Test Teardown") -if (Passed && any_routines_with_error()) { - Passed = false; - raise << Current_scenario->name << ": some routines died with errors\n" << end(); -} - -:(code) -bool any_routines_with_error() { - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->state == DISCONTINUED) - return true; - } - return false; -} - -:(before "End routine Fields") -int limit; -:(before "End routine Constructor") -limit = -1; /* no limit */ - -:(before "End Primitive Recipe Declarations") -LIMIT_TIME, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "limit-time", LIMIT_TIME); -:(before "End Primitive Recipe Checks") -case LIMIT_TIME: { - if (SIZE(inst.ingredients) != 2) { - raise << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'limit-time' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(1))) { - raise << maybe(get(Recipe, r).name) << "second ingredient of 'limit-time' should be a number (of instructions to run for), but got '" << inst.ingredients.at(1).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case LIMIT_TIME: { - int id = ingredients.at(0).at(0); - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->id == id) { - Routines.at(i)->limit = ingredients.at(1).at(0); - break; - } - } - break; -} - -:(before "End routine Fields") -int ninstrs; -:(before "End routine Constructor") -ninstrs = 0; -:(after "stop_running_current_routine:") -Current_routine->ninstrs += ninstrs; -:(before "End Primitive Recipe Declarations") -NUMBER_OF_INSTRUCTIONS, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "number-of-instructions", NUMBER_OF_INSTRUCTIONS); -:(before "End Primitive Recipe Checks") -case NUMBER_OF_INSTRUCTIONS: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'number-of-instructions' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'number-of-instructions' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case NUMBER_OF_INSTRUCTIONS: { - int id = ingredients.at(0).at(0); - int result = -1; - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->id == id) { - result = Routines.at(i)->ninstrs; - break; - } - } - products.resize(1); - products.at(0).push_back(result); - break; -} - -:(scenario number_of_instructions) -def f1 [ - 10:number/child-id <- start-running f2 - { - loop-unless 20:number - } - 11:number <- number-of-instructions 10:number -] -def f2 [ - # 2 instructions worth of work - 1:number <- copy 34 - 20:number <- copy 1 -] -# f2 runs an extra instruction for the implicit return added by the -# fill_in_reply_ingredients transform -+mem: storing 3 in location 11 - -:(scenario number_of_instructions_across_multiple_scheduling_intervals) -% Scheduling_interval = 1; -def f1 [ - 10:number/child-id <- start-running f2 - { - loop-unless 20:number - } - 11:number <- number-of-instructions 10:number -] -def f2 [ - # 4 instructions worth of work - 1:number <- copy 34 - 2:number <- copy 1 - 2:number <- copy 3 - 20:number <- copy 1 -] -# f2 runs an extra instruction for the implicit return added by the -# fill_in_reply_ingredients transform -+mem: storing 5 in location 11 - -//:: make sure that each routine gets a different alloc to start - -:(scenario new_concurrent) -def f1 [ - start-running f2 - 1:address:number/raw <- new number:type - # wait for f2 to complete - { - loop-unless 4:number/raw - } -] -def f2 [ - 2:address:number/raw <- new number:type - # hack: assumes scheduler implementation - 3:boolean/raw <- equal 1:address:number/raw, 2:address:number/raw - # signal f2 complete - 4:number/raw <- copy 1 -] -+mem: storing 0 in location 3 diff --git a/072scheduler.cc b/072scheduler.cc new file mode 100644 index 00000000..99d5488b --- /dev/null +++ b/072scheduler.cc @@ -0,0 +1,625 @@ +//: Run a second routine concurrently using 'start-running', without any +//: guarantees on how the operations in each are interleaved with each other. + +:(scenario scheduler) +def f1 [ + start-running f2 + # wait for f2 to run + { + jump-unless 1:number, -1 + } +] +def f2 [ + 1:number <- copy 1 +] ++schedule: f1 ++schedule: f2 + +//: first, add a deadline to run(routine) +//: these changes are ugly and brittle; just close your nose and get through the next few lines +:(replace "void run_current_routine()") +void run_current_routine(int time_slice) +:(replace "while (!Current_routine->completed())" following "void run_current_routine(int time_slice)") +int ninstrs = 0; +while (Current_routine->state == RUNNING && ninstrs < time_slice) +:(after "Running One Instruction") +ninstrs++; + +//: now the rest of the scheduler is clean + +:(before "struct routine") +enum routine_state { + RUNNING, + COMPLETED, + // End routine States +}; +:(before "End routine Fields") +enum routine_state state; +:(before "End routine Constructor") +state = RUNNING; + +:(before "End Globals") +vector Routines; +int Current_routine_index = 0; +int Scheduling_interval = 500; +:(before "End Setup") +Scheduling_interval = 500; +Routines.clear(); +:(replace{} "void run(recipe_ordinal r)") +void run(recipe_ordinal r) { + run(new routine(r)); +} + +:(code) +void run(routine* rr) { + Routines.push_back(rr); + Current_routine_index = 0, Current_routine = Routines.at(0); + while (!all_routines_done()) { + skip_to_next_routine(); + assert(Current_routine); + assert(Current_routine->state == RUNNING); + trace(9990, "schedule") << current_routine_label() << end(); + run_current_routine(Scheduling_interval); + // Scheduler State Transitions + if (Current_routine->completed()) + Current_routine->state = COMPLETED; + // End Scheduler State Transitions + + // Scheduler Cleanup + // End Scheduler Cleanup + } +} + +bool all_routines_done() { + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state == RUNNING) + return false; + } + return true; +} + +// skip Current_routine_index past non-RUNNING routines +void skip_to_next_routine() { + assert(!Routines.empty()); + assert(Current_routine_index < SIZE(Routines)); + for (int i = (Current_routine_index+1)%SIZE(Routines); i != Current_routine_index; i = (i+1)%SIZE(Routines)) { + if (Routines.at(i)->state == RUNNING) { + Current_routine_index = i; + Current_routine = Routines.at(i); + return; + } + } +} + +string current_routine_label() { + ostringstream result; + const call_stack& calls = Current_routine->calls; + for (call_stack::const_iterator p = calls.begin(); p != calls.end(); ++p) { + if (p != calls.begin()) result << '/'; + result << get(Recipe, p->running_recipe).name; + } + return result.str(); +} + +:(before "End Teardown") +for (int i = 0; i < SIZE(Routines); ++i) + delete Routines.at(i); +Routines.clear(); +Current_routine = NULL; + +//: special case for the very first routine +:(replace{} "void run_main(int argc, char* argv[])") +void run_main(int argc, char* argv[]) { + recipe_ordinal r = get(Recipe_ordinal, "main"); + assert(r); + routine* main_routine = new routine(r); + // pass in commandline args as ingredients to main + // todo: test this + Current_routine = main_routine; + for (int i = 1; i < argc; ++i) { + vector arg; + arg.push_back(new_mu_string(argv[i])); + current_call().ingredient_atoms.push_back(arg); + } + run(main_routine); +} + +//:: To schedule new routines to run, call 'start-running'. + +//: 'start-running' will return a unique id for the routine that was created. +//: routine id is a number, but don't do any arithmetic on it +:(before "End routine Fields") +int id; +:(before "End Globals") +int Next_routine_id = 1; +:(before "End Setup") +Next_routine_id = 1; +:(before "End routine Constructor") +id = Next_routine_id; +Next_routine_id++; + +//: routines save the routine that spawned them +:(before "End routine Fields") +// todo: really should be routine_id, but that's less efficient. +int parent_index; // only < 0 if there's no parent_index +:(before "End routine Constructor") +parent_index = -1; + +:(before "End Primitive Recipe Declarations") +START_RUNNING, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "start-running", START_RUNNING); +:(before "End Primitive Recipe Checks") +case START_RUNNING: { + if (inst.ingredients.empty()) { + raise << maybe(get(Recipe, r).name) << "'start-running' requires at least one ingredient: the recipe to start running\n" << end(); + break; + } + if (!is_mu_recipe(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'start-running' should be a recipe, but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case START_RUNNING: { + routine* new_routine = new routine(ingredients.at(0).at(0)); + new_routine->parent_index = Current_routine_index; + // populate ingredients + for (int i = 1; i < SIZE(current_instruction().ingredients); ++i) { + new_routine->calls.front().ingredient_atoms.push_back(ingredients.at(i)); + reagent/*copy*/ ingredient = current_instruction().ingredients.at(i); + canonize_type(ingredient); + new_routine->calls.front().ingredients.push_back(ingredient); + } + Routines.push_back(new_routine); + products.resize(1); + products.at(0).push_back(new_routine->id); + break; +} + +:(scenario scheduler_runs_single_routine) +% Scheduling_interval = 1; +def f1 [ + 1:number <- copy 0 + 2:number <- copy 0 +] ++schedule: f1 ++run: {1: "number"} <- copy {0: "literal"} ++schedule: f1 ++run: {2: "number"} <- copy {0: "literal"} + +:(scenario scheduler_interleaves_routines) +% Scheduling_interval = 1; +def f1 [ + start-running f2 + 1:number <- copy 0 + 2:number <- copy 0 +] +def f2 [ + 3:number <- copy 0 + 4:number <- copy 0 +] ++schedule: f1 ++run: start-running {f2: "recipe-literal"} ++schedule: f2 ++run: {3: "number"} <- copy {0: "literal"} ++schedule: f1 ++run: {1: "number"} <- copy {0: "literal"} ++schedule: f2 ++run: {4: "number"} <- copy {0: "literal"} ++schedule: f1 ++run: {2: "number"} <- copy {0: "literal"} + +:(scenario start_running_takes_ingredients) +def f1 [ + start-running f2, 3 + # wait for f2 to run + { + jump-unless 1:number, -1 + } +] +def f2 [ + 1:number <- next-ingredient + 2:number <- add 1:number, 1 +] ++mem: storing 4 in location 2 + +:(scenario start_running_returns_routine_id) +def f1 [ + 1:number <- start-running f2 +] +def f2 [ + 12:number <- copy 44 +] ++mem: storing 2 in location 1 + +//: this scenario will require some careful setup in escaped C++ +//: (straining our tangle capabilities to near-breaking point) +:(scenario scheduler_skips_completed_routines) +% recipe_ordinal f1 = load("recipe f1 [\n1:number <- copy 0\n]\n").front(); +% recipe_ordinal f2 = load("recipe f2 [\n2:number <- copy 0\n]\n").front(); +% Routines.push_back(new routine(f1)); // f1 meant to run +% Routines.push_back(new routine(f2)); +% Routines.back()->state = COMPLETED; // f2 not meant to run +# must have at least one routine without escaping +def f3 [ + 3:number <- copy 0 +] +# by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order ++schedule: f1 ++mem: storing 0 in location 1 +-schedule: f2 +-mem: storing 0 in location 2 ++schedule: f3 ++mem: storing 0 in location 3 + +:(scenario scheduler_starts_at_middle_of_routines) +% Routines.push_back(new routine(COPY)); +% Routines.back()->state = COMPLETED; +def f1 [ + 1:number <- copy 0 + 2:number <- copy 0 +] ++schedule: f1 +-run: idle + +//:: Errors in a routine cause it to terminate. + +:(scenario scheduler_terminates_routines_after_errors) +% Hide_errors = true; +% Scheduling_interval = 2; +def f1 [ + start-running f2 + 1:number <- copy 0 + 2:number <- copy 0 +] +def f2 [ + # divide by 0 twice + 3:number <- divide-with-remainder 4, 0 + 4:number <- divide-with-remainder 4, 0 +] +# f2 should stop after first divide by 0 ++error: f2: divide by zero in '3:number <- divide-with-remainder 4, 0' +-error: f2: divide by zero in '4:number <- divide-with-remainder 4, 0' + +:(after "operator<<(ostream& os, unused end)") + if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) { + Current_routine->state = COMPLETED; + } + +//:: Routines are marked completed when their parent completes. + +:(scenario scheduler_kills_orphans) +def main [ + start-running f1 + # f1 never actually runs because its parent completes without waiting for it +] +def f1 [ + 1:number <- copy 0 +] +-schedule: f1 + +:(before "End Scheduler Cleanup") +for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state == COMPLETED) continue; + if (Routines.at(i)->parent_index < 0) continue; // root thread + if (has_completed_parent(i)) { + Routines.at(i)->state = COMPLETED; + } +} + +:(code) +bool has_completed_parent(int routine_index) { + for (int j = routine_index; j >= 0; j = Routines.at(j)->parent_index) { + if (Routines.at(j)->state == COMPLETED) + return true; + } + return false; +} + +//:: 'routine-state' can tell if a given routine id is running + +:(scenario routine_state_test) +% Scheduling_interval = 2; +def f1 [ + 1:number/child-id <- start-running f2 + 12:number <- copy 0 # race condition since we don't care about location 12 + # thanks to Scheduling_interval, f2's one instruction runs in between here and completes + 2:number/state <- routine-state 1:number/child-id +] +def f2 [ + 12:number <- copy 0 + # trying to run a second instruction marks routine as completed +] +# recipe f2 should be in state COMPLETED ++mem: storing 1 in location 2 + +:(before "End Primitive Recipe Declarations") +ROUTINE_STATE, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "routine-state", ROUTINE_STATE); +:(before "End Primitive Recipe Checks") +case ROUTINE_STATE: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'routine-state' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case ROUTINE_STATE: { + int id = ingredients.at(0).at(0); + int result = -1; + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->id == id) { + result = Routines.at(i)->state; + break; + } + } + products.resize(1); + products.at(0).push_back(result); + break; +} + +//:: miscellaneous helpers + +:(before "End Primitive Recipe Declarations") +RESTART, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "restart", RESTART); +:(before "End Primitive Recipe Checks") +case RESTART: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'restart' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case RESTART: { + int id = ingredients.at(0).at(0); + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->id == id) { + Routines.at(i)->state = RUNNING; + break; + } + } + break; +} + +:(before "End Primitive Recipe Declarations") +STOP, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "stop", STOP); +:(before "End Primitive Recipe Checks") +case STOP: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'stop' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case STOP: { + int id = ingredients.at(0).at(0); + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->id == id) { + Routines.at(i)->state = COMPLETED; + break; + } + } + break; +} + +:(before "End Primitive Recipe Declarations") +_DUMP_ROUTINES, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES); +:(before "End Primitive Recipe Checks") +case _DUMP_ROUTINES: { + break; +} +:(before "End Primitive Recipe Implementations") +case _DUMP_ROUTINES: { + for (int i = 0; i < SIZE(Routines); ++i) { + cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n'; + } + break; +} + +//: support for stopping routines after some number of cycles + +:(scenario routine_discontinues_past_limit) +% Scheduling_interval = 2; +def f1 [ + 1:number/child-id <- start-running f2 + limit-time 1:number/child-id, 10 + # padding loop just to make sure f2 has time to completed + 2:number <- copy 20 + 2:number <- subtract 2:number, 1 + jump-if 2:number, -2:offset +] +def f2 [ + jump -1:offset # run forever + $print [should never get here], 10/newline +] +# f2 terminates ++schedule: discontinuing routine 2 + +:(before "End routine States") +DISCONTINUED, +:(before "End Scheduler State Transitions") +if (Current_routine->limit >= 0) { + if (Current_routine->limit <= Scheduling_interval) { + trace(9999, "schedule") << "discontinuing routine " << Current_routine->id << end(); + Current_routine->state = DISCONTINUED; + Current_routine->limit = 0; + } + else { + Current_routine->limit -= Scheduling_interval; + } +} + +:(before "End Test Teardown") +if (Passed && any_routines_with_error()) { + Passed = false; + raise << "some routines died with errors\n" << end(); +} +:(before "End Mu Test Teardown") +if (Passed && any_routines_with_error()) { + Passed = false; + raise << Current_scenario->name << ": some routines died with errors\n" << end(); +} + +:(code) +bool any_routines_with_error() { + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state == DISCONTINUED) + return true; + } + return false; +} + +:(before "End routine Fields") +int limit; +:(before "End routine Constructor") +limit = -1; /* no limit */ + +:(before "End Primitive Recipe Declarations") +LIMIT_TIME, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "limit-time", LIMIT_TIME); +:(before "End Primitive Recipe Checks") +case LIMIT_TIME: { + if (SIZE(inst.ingredients) != 2) { + raise << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'limit-time' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(1))) { + raise << maybe(get(Recipe, r).name) << "second ingredient of 'limit-time' should be a number (of instructions to run for), but got '" << inst.ingredients.at(1).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case LIMIT_TIME: { + int id = ingredients.at(0).at(0); + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->id == id) { + Routines.at(i)->limit = ingredients.at(1).at(0); + break; + } + } + break; +} + +:(before "End routine Fields") +int ninstrs; +:(before "End routine Constructor") +ninstrs = 0; +:(after "stop_running_current_routine:") +Current_routine->ninstrs += ninstrs; +:(before "End Primitive Recipe Declarations") +NUMBER_OF_INSTRUCTIONS, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "number-of-instructions", NUMBER_OF_INSTRUCTIONS); +:(before "End Primitive Recipe Checks") +case NUMBER_OF_INSTRUCTIONS: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'number-of-instructions' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'number-of-instructions' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case NUMBER_OF_INSTRUCTIONS: { + int id = ingredients.at(0).at(0); + int result = -1; + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->id == id) { + result = Routines.at(i)->ninstrs; + break; + } + } + products.resize(1); + products.at(0).push_back(result); + break; +} + +:(scenario number_of_instructions) +def f1 [ + 10:number/child-id <- start-running f2 + { + loop-unless 20:number + } + 11:number <- number-of-instructions 10:number +] +def f2 [ + # 2 instructions worth of work + 1:number <- copy 34 + 20:number <- copy 1 +] +# f2 runs an extra instruction for the implicit return added by the +# fill_in_reply_ingredients transform ++mem: storing 3 in location 11 + +:(scenario number_of_instructions_across_multiple_scheduling_intervals) +% Scheduling_interval = 1; +def f1 [ + 10:number/child-id <- start-running f2 + { + loop-unless 20:number + } + 11:number <- number-of-instructions 10:number +] +def f2 [ + # 4 instructions worth of work + 1:number <- copy 34 + 2:number <- copy 1 + 2:number <- copy 3 + 20:number <- copy 1 +] +# f2 runs an extra instruction for the implicit return added by the +# fill_in_reply_ingredients transform ++mem: storing 5 in location 11 + +//:: make sure that each routine gets a different alloc to start + +:(scenario new_concurrent) +def f1 [ + start-running f2 + 1:address:number/raw <- new number:type + # wait for f2 to complete + { + loop-unless 4:number/raw + } +] +def f2 [ + 2:address:number/raw <- new number:type + # hack: assumes scheduler implementation + 3:boolean/raw <- equal 1:address:number/raw, 2:address:number/raw + # signal f2 complete + 4:number/raw <- copy 1 +] ++mem: storing 0 in location 3 diff --git a/072wait.cc b/072wait.cc deleted file mode 100644 index 584e88e3..00000000 --- a/072wait.cc +++ /dev/null @@ -1,329 +0,0 @@ -//: Routines can be put in a 'waiting' state, from which it will be ready to -//: run again when a specific memory location changes its value. This is mu's -//: basic technique for orchestrating the order in which different routines -//: operate. - -:(scenario wait_for_location) -def f1 [ - 1:number <- copy 0 - start-running f2 - 2:location <- copy 1/unsafe - wait-for-location 2:location - # now wait for f2 to run and modify location 1 before using its value - 3:number <- copy 1:number -] -def f2 [ - 1:number <- copy 34 -] -# if we got the synchronization wrong we'd be storing 0 in location 3 -+mem: storing 34 in location 3 - -//: define the new state that all routines can be in - -:(before "End routine States") -WAITING, -:(before "End routine Fields") -// only if state == WAITING -int waiting_on_location; -int old_value_of_waiting_location; -:(before "End routine Constructor") -waiting_on_location = old_value_of_waiting_location = 0; - -:(before "End Mu Test Teardown") -if (Passed && any_routines_waiting()) { - Passed = false; - raise << Current_scenario->name << ": deadlock!\n" << end(); -} -:(before "End Test Teardown") -if (Passed && any_routines_with_error()) { - Passed = false; - raise << "some routines died with errors\n" << end(); -} -:(code) -bool any_routines_waiting() { - for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->state == WAITING) - return true; - } - return false; -} - -//: primitive recipe to put routines in that state - -:(before "End Primitive Recipe Declarations") -WAIT_FOR_LOCATION, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "wait-for-location", WAIT_FOR_LOCATION); -:(before "End Primitive Recipe Checks") -case WAIT_FOR_LOCATION: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'wait-for-location' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_location(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "'wait-for-location' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - } - break; -} -:(before "End Primitive Recipe Implementations") -case WAIT_FOR_LOCATION: { - int loc = ingredients.at(0).at(0); - Current_routine->state = WAITING; - Current_routine->waiting_on_location = loc; - Current_routine->old_value_of_waiting_location = get_or_insert(Memory, loc); - trace(9998, "run") << "waiting for location " << loc << " to change from " << no_scientific(get_or_insert(Memory, loc)) << end(); - break; -} - -//: scheduler tweak to get routines out of that state - -:(before "End Scheduler State Transitions") -for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->state != WAITING) continue; - if (Routines.at(i)->waiting_on_location && - get_or_insert(Memory, Routines.at(i)->waiting_on_location) != Routines.at(i)->old_value_of_waiting_location) { - trace(9999, "schedule") << "waking up routine\n" << end(); - Routines.at(i)->state = RUNNING; - Routines.at(i)->waiting_on_location = Routines.at(i)->old_value_of_waiting_location = 0; - } -} - -//: primitive to help compute locations to wait for -//: only supports elements inside containers, no arrays or containers within -//: containers yet. - -:(scenario get_location) -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 15:location <- get-location 12:point, 1:offset -] -+mem: storing 13 in location 15 - -:(before "End Primitive Recipe Declarations") -GET_LOCATION, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "get-location", GET_LOCATION); -:(before "End Primitive Recipe Checks") -case GET_LOCATION: { - if (SIZE(inst.ingredients) != 2) { - raise << maybe(get(Recipe, r).name) << "'get-location' expects exactly 2 ingredients in '" << inst.original_string << "'\n" << end(); - break; - } - reagent/*copy*/ base = inst.ingredients.at(0); - if (!canonize_type(base)) break; - if (!base.type || !base.type->value || !contains_key(Type, base.type->value) || get(Type, base.type->value).kind != CONTAINER) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'get-location' should be a container, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - type_ordinal base_type = base.type->value; - const reagent& offset = inst.ingredients.at(1); - if (!is_literal(offset) || !is_mu_scalar(offset)) { - raise << maybe(get(Recipe, r).name) << "second ingredient of 'get-location' should have type 'offset', but got '" << inst.ingredients.at(1).original_string << "'\n" << end(); - break; - } - int offset_value = 0; - if (is_integer(offset.name)) { // later layers permit non-integer offsets - offset_value = to_integer(offset.name); - if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { - raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for '" << get(Type, base_type).name << "'\n" << end(); - break; - } - } - else { - offset_value = offset.value; - } - if (inst.products.empty()) break; - if (!is_mu_location(inst.products.at(0))) { - raise << maybe(get(Recipe, r).name) << "'get-location " << base.original_string << ", " << offset.original_string << "' should write to type location but '" << inst.products.at(0).name << "' has type '" << names_to_string_without_quotes(inst.products.at(0).type) << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case GET_LOCATION: { - reagent/*copy*/ base = current_instruction().ingredients.at(0); - canonize(base); - int base_address = base.value; - if (base_address == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - type_ordinal base_type = base.type->value; - int offset = ingredients.at(1).at(0); - if (offset < 0 || offset >= SIZE(get(Type, base_type).elements)) break; // copied from Check above - int result = base_address; - for (int i = 0; i < offset; ++i) - result += size_of(element_type(base.type, i)); - trace(9998, "run") << "address to copy is " << result << end(); - products.resize(1); - products.at(0).push_back(result); - break; -} - -:(code) -bool is_mu_location(reagent/*copy*/ x) { - if (!canonize_type(x)) return false; - if (!x.type) return false; - if (x.type->right) return false; - return x.type->value == get(Type_ordinal, "location"); -} - -:(scenario get_location_out_of_bounds) -% Hide_errors = true; -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - get-location 12:point-number/raw, 2:offset # point-number occupies 3 locations but has only 2 fields; out of bounds -] -+error: main: invalid offset 2 for 'point-number' - -:(scenario get_location_out_of_bounds_2) -% Hide_errors = true; -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - get-location 12:point-number/raw, -1:offset -] -+error: main: invalid offset -1 for 'point-number' - -:(scenario get_location_product_type_mismatch) -% Hide_errors = true; -container boolbool [ - x:boolean - y:boolean -] -def main [ - 12:boolean <- copy 1 - 13:boolean <- copy 0 - 15:boolean <- get-location 12:boolbool, 1:offset -] -+error: main: 'get-location 12:boolbool, 1:offset' should write to type location but '15' has type 'boolean' - -:(scenario get_location_indirect) -# 'get-location' can read from container address -def main [ - 1:number <- copy 10 - # 10 reserved for refcount - 11:number <- copy 34 - 12:number <- copy 35 - 4:location <- get-location 1:address:point/lookup, 0:offset -] -+mem: storing 11 in location 4 - -:(scenario get_location_indirect_2) -def main [ - 1:number <- copy 10 - # 10 reserved for refcount - 11:number <- copy 34 - 12:number <- copy 35 - 4:address:number <- copy 20/unsafe - 4:address:location/lookup <- get-location 1:address:point/lookup, 0:offset -] -+mem: storing 11 in location 21 - -//: also allow waiting on a routine to stop running - -:(scenario wait_for_routine) -def f1 [ - 1:number <- copy 0 - 12:number/routine <- start-running f2 - wait-for-routine 12:number/routine - # now wait for f2 to run and modify location 1 before using its value - 3:number <- copy 1:number -] -def f2 [ - 1:number <- copy 34 -] -+schedule: f1 -+run: waiting for routine 2 -+schedule: f2 -+schedule: waking up routine 1 -+schedule: f1 -# if we got the synchronization wrong we'd be storing 0 in location 3 -+mem: storing 34 in location 3 - -:(before "End routine Fields") -// only if state == WAITING -int waiting_on_routine; -:(before "End routine Constructor") -waiting_on_routine = 0; - -:(before "End Primitive Recipe Declarations") -WAIT_FOR_ROUTINE, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE); -:(before "End Primitive Recipe Checks") -case WAIT_FOR_ROUTINE: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case WAIT_FOR_ROUTINE: { - if (ingredients.at(0).at(0) == Current_routine->id) { - raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - Current_routine->state = WAITING; - Current_routine->waiting_on_routine = ingredients.at(0).at(0); - trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end(); - break; -} - -:(before "End Scheduler State Transitions") -// Wake up any routines waiting for other routines to go to sleep. -// Important: this must come after the scheduler loop above giving routines -// waiting for locations to change a chance to wake up. -for (int i = 0; i < SIZE(Routines); ++i) { - if (Routines.at(i)->state != WAITING) continue; - if (!Routines.at(i)->waiting_on_routine) continue; - int id = Routines.at(i)->waiting_on_routine; - assert(id != Routines.at(i)->id); // routine can't wait on itself - for (int j = 0; j < SIZE(Routines); ++j) { - if (Routines.at(j)->id == id && Routines.at(j)->state != RUNNING) { - trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end(); - Routines.at(i)->state = RUNNING; - Routines.at(i)->waiting_on_routine = 0; - } - } -} - -:(before "End Primitive Recipe Declarations") -SWITCH, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "switch", SWITCH); -:(before "End Primitive Recipe Checks") -case SWITCH: { - break; -} -:(before "End Primitive Recipe Implementations") -case SWITCH: { - int id = some_other_running_routine(); - if (id) { - assert(id != Current_routine->id); - Current_routine->state = WAITING; - Current_routine->waiting_on_routine = id; - } - break; -} - -:(code) -int some_other_running_routine() { - for (int i = 0; i < SIZE(Routines); ++i) { - if (i == Current_routine_index) continue; - assert(Routines.at(i) != Current_routine); - assert(Routines.at(i)->id != Current_routine->id); - if (Routines.at(i)->state == RUNNING) - return Routines.at(i)->id; - } - return 0; -} diff --git a/073deep_copy.cc b/073deep_copy.cc deleted file mode 100644 index 59f71286..00000000 --- a/073deep_copy.cc +++ /dev/null @@ -1,387 +0,0 @@ -// To recursively copy containers and any addresses they contain, use -// 'deep-copy'. -// -// Invariant: After a deep-copy its ingredient and result will point to no -// common addresses. -// Implications: Refcounts of all data pointed to by the original ingredient -// will remain unchanged. Refcounts of all data pointed to by the (newly -// created) result will be 1, in the absence of cycles. -// -// We do handle cycles in the ingredient, however. All cycles are translated -// to new cycles in the product. - -:(scenario deep_copy_number) -def main [ - local-scope - x:number <- copy 34 - y:number <- deep-copy x - 10:boolean/raw <- equal x, y -] -# non-address primitives are identical -+mem: storing 1 in location 10 - -:(scenario deep_copy_container_without_address) -container foo [ - x:number - y:number -] -def main [ - local-scope - a:foo <- merge 34, 35 - b:foo <- deep-copy a - 10:boolean/raw <- equal a, b -] -# containers are identical as long as they don't contain addresses -+mem: storing 1 in location 10 - -:(scenario deep_copy_address) -% Memory_allocated_until = 200; -def main [ - # avoid all memory allocations except the implicit ones inside deep-copy, so - # that the result is deterministic - 1:address:number <- copy 100/unsafe # pretend allocation - *1:address:number <- copy 34 - 2:address:number <- deep-copy 1:address:number - 10:boolean <- equal 1:address:number, 2:address:number - 11:boolean <- equal *1:address:number, *2:address:number - 2:address:number <- copy 0 -] -# the result of deep-copy is a new address -+mem: storing 0 in location 10 -# however, the contents are identical -+mem: storing 1 in location 11 -# the result of deep-copy gets a refcount of 1 -# (its address 202 = 200 base + 2 for temporary space inside deep-copy) -+run: {2: ("address" "number")} <- copy {0: "literal"} -+mem: decrementing refcount of 202: 1 -> 0 -+abandon: saving 202 in free-list of size 2 - -:(scenario deep_copy_address_to_container) -% Memory_allocated_until = 200; -def main [ - # avoid all memory allocations except the implicit ones inside deep-copy, so - # that the result is deterministic - 1:address:point <- copy 100/unsafe # pretend allocation - *1:address:point <- merge 34, 35 - 2:address:point <- deep-copy 1:address:point - 10:boolean <- equal 1:address:point, 2:address:point - 11:boolean <- equal *1:address:point, *2:address:point -] -# the result of deep-copy is a new address -+mem: storing 0 in location 10 -# however, the contents are identical -+mem: storing 1 in location 11 - -:(scenario deep_copy_address_to_address) -% Memory_allocated_until = 200; -def main [ - # avoid all memory allocations except the implicit ones inside deep-copy, so - # that the result is deterministic - 1:address:address:number <- copy 100/unsafe # pretend allocation - *1:address:address:number <- copy 150/unsafe - **1:address:address:number <- copy 34 - 2:address:address:number <- deep-copy 1:address:address:number - 10:boolean <- equal 1:address:address:number, 2:address:address:number - 11:boolean <- equal *1:address:address:number, *2:address:address:number - 12:boolean <- equal **1:address:address:number, **2:address:address:number -] -# the result of deep-copy is a new address -+mem: storing 0 in location 10 -# any addresses in it or pointed to it are also new -+mem: storing 0 in location 11 -# however, the non-address contents are identical -+mem: storing 1 in location 12 - -:(scenario deep_copy_array) -% Memory_allocated_until = 200; -def main [ - # avoid all memory allocations except the implicit ones inside deep-copy, so - # that the result is deterministic - 100:number <- copy 1 # pretend refcount - 101:number <- copy 3 # pretend array length - 1:address:array:number <- copy 100/unsafe # pretend allocation - put-index *1:address:array:number, 0, 34 - put-index *1:address:array:number, 1, 35 - put-index *1:address:array:number, 2, 36 - stash [old:], *1:address:array:number - 2:address:array:number <- deep-copy 1:address:array:number - stash 2:address:array:number - stash [new:], *2:address:array:number - 10:boolean <- equal 1:address:array:number, 2:address:array:number - 11:boolean <- equal *1:address:array:number, *2:address:array:number -] -+app: old: 3 34 35 36 -+app: new: 3 34 35 36 -# the result of deep-copy is a new address -+mem: storing 0 in location 10 -# however, the contents are identical -+mem: storing 1 in location 11 - -:(scenario deep_copy_container_with_address) -container foo [ - x:number - y:address:number -] -def main [ - local-scope - y0:address:number <- new number:type - *y0 <- copy 35 - a:foo <- merge 34, y0 - b:foo <- deep-copy a - 10:boolean/raw <- equal a, b - y1:address:number <- get b, y:offset - 11:boolean/raw <- equal y0, y1 - 12:number/raw <- copy *y1 -] -# containers containing addresses are not identical to their deep copies -+mem: storing 0 in location 10 -# the addresses they contain are not identical either -+mem: storing 0 in location 11 -+mem: storing 35 in location 12 - -:(scenario deep_copy_exclusive_container_with_address) -exclusive-container foo [ - x:number - y:address:number -] -def main [ - local-scope - y0:address:number <- new number:type - *y0 <- copy 34 - a:foo <- merge 1/y, y0 - b:foo <- deep-copy a - 10:boolean/raw <- equal a, b - y1:address:number, z:boolean <- maybe-convert b, y:variant - 11:boolean/raw <- equal y0, y1 - 12:number/raw <- copy *y1 -] -# exclusive containers containing addresses are not identical to their deep copies -+mem: storing 0 in location 10 -# the addresses they contain are not identical either -+mem: storing 0 in location 11 -+mem: storing 34 in location 12 - -:(scenario deep_copy_exclusive_container_with_container_with_address) -exclusive-container foo [ - x:number - y:bar # inline -] -container bar [ - x:address:number -] -def main [ - local-scope - y0:address:number <- new number:type - *y0 <- copy 34 - a:bar <- merge y0 - b:foo <- merge 1/y, a - c:foo <- deep-copy b - 10:boolean/raw <- equal b, c - d:bar, z:boolean <- maybe-convert c, y:variant - y1:address:number <- get d, x:offset - 11:boolean/raw <- equal y0, y1 - 12:number/raw <- copy *y1 -] -# exclusive containers containing addresses are not identical to their deep copies -+mem: storing 0 in location 10 -# sub-containers containing addresses are not identical either -+mem: storing 0 in location 11 -+mem: storing 34 in location 12 - -:(before "End Primitive Recipe Declarations") -DEEP_COPY, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "deep-copy", DEEP_COPY); -:(before "End Primitive Recipe Checks") -case DEEP_COPY: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); - break; - } - if (SIZE(inst.products) != 1) { - raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); - break; - } - if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) { - raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << inst.original_string << "'\n" << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case DEEP_COPY: { - const reagent& input = current_instruction().ingredients.at(0); - // allocate a tiny bit of temporary space for deep_copy() - trace(9991, "run") << "deep-copy: allocating space for temporary" << end(); - reagent tmp("tmp:address:number"); - tmp.value = allocate(1); - products.push_back(deep_copy(input, tmp)); - // reclaim Mu memory allocated for tmp - trace(9991, "run") << "deep-copy: reclaiming temporary" << end(); - abandon(tmp.value, tmp.type->right, payload_size(tmp)); - // reclaim host memory allocated for tmp.type when tmp goes out of scope - break; -} - -:(code) -vector deep_copy(const reagent& in, const reagent& tmp) { - map addresses_copied; - return deep_copy(in, addresses_copied, tmp); -} - -vector deep_copy(reagent/*copy*/ in, map& addresses_copied, const reagent& tmp) { - canonize(in); - vector result; - if (is_mu_address(in)) - result.push_back(deep_copy_address(in, addresses_copied, tmp)); - else - deep_copy(in, addresses_copied, tmp, result); - return result; -} - -// deep-copy an address and return a new address -int deep_copy_address(const reagent& canonized_in, map& addresses_copied, const reagent& tmp) { - if (canonized_in.value == 0) return 0; - int in_address = payload_address(canonized_in); - trace(9991, "run") << "deep-copy: copying address " << in_address << end(); - if (contains_key(addresses_copied, in_address)) { - int out = get(addresses_copied, in_address); - trace(9991, "run") << "deep-copy: copy already exists: " << out << end(); - return out; - } - int out = allocate(payload_size(canonized_in)); - trace(9991, "run") << "deep-copy: new address is " << out << end(); - put(addresses_copied, in_address, out); - reagent/*copy*/ payload = canonized_in; - payload.properties.push_back(pair("lookup", NULL)); - trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end(); - vector data = deep_copy(payload, addresses_copied, tmp); - trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end(); - // HACK: write_memory interface isn't ideal for this situation; we need - // a temporary location to help copy the payload. - trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end(); - put(Memory, tmp.value, out); - payload.value = tmp.value; // now modified for output - vector old_data = read_memory(payload); - trace(9991, "run") << "deep-copy: really writing to " << payload.value << ' ' << to_string(payload) << " (old value " << to_string(old_data) << " new value " << to_string(data) << ")" << end(); - write_memory(payload, data, -1); - trace(9991, "run") << "deep-copy: output is " << to_string(data) << end(); - return out; -} - -// deep-copy a non-address and return a vector of locations -void deep_copy(const reagent& canonized_in, map& addresses_copied, const reagent& tmp, vector& out) { - assert(!is_mu_address(canonized_in)); - vector data = read_memory(canonized_in); - out.insert(out.end(), data.begin(), data.end()); - if (!contains_key(Container_metadata, canonized_in.type)) return; - trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end(); - const container_metadata& metadata = get(Container_metadata, canonized_in.type); - for (map, set >::const_iterator p = metadata.address.begin(); p != metadata.address.end(); ++p) { - if (!all_match(data, p->first)) continue; - for (set::const_iterator info = p->second.begin(); info != p->second.end(); ++info) { - // construct a fake reagent that reads directly from the appropriate - // field of the container - reagent curr; - curr.type = new type_tree("address", new type_tree(*info->payload_type)); - curr.set_value(canonized_in.value + info->offset); - curr.properties.push_back(pair("raw", NULL)); - trace(9991, "run") << "deep-copy: copying address " << curr.value << end(); - out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp); - } - } -} - -int payload_address(reagent/*copy*/ x) { - x.properties.push_back(pair("lookup", NULL)); - canonize(x); - return x.value; -} - -//: moar tests, just because I can't believe it all works - -:(scenario deep_copy_stress_test_1) -container foo1 [ - p:address:number -] -container foo2 [ - p:address:foo1 -] -exclusive-container foo3 [ - p:address:foo1 - q:address:foo2 -] -def main [ - local-scope - x:address:number <- new number:type - *x <- copy 34 - a:address:foo1 <- new foo1:type - *a <- merge x - b:address:foo2 <- new foo2:type - *b <- merge a - c:foo3 <- merge 1/q, b - d:foo3 <- deep-copy c - e:address:foo2, z:boolean <- maybe-convert d, q:variant - f:address:foo1 <- get *e, p:offset - g:address:number <- get *f, p:offset - 1:number/raw <- copy *g -] -+mem: storing 34 in location 1 - -:(scenario deep_copy_stress_test_2) -container foo1 [ - p:address:number -] -container foo2 [ - p:address:foo1 -] -exclusive-container foo3 [ - p:address:foo1 - q:address:foo2 -] -container foo4 [ - p:number - q:address:foo3 -] -def main [ - local-scope - x:address:number <- new number:type - *x <- copy 34 - a:address:foo1 <- new foo1:type - *a <- merge x - b:address:foo2 <- new foo2:type - *b <- merge a - c:address:foo3 <- new foo3:type - *c <- merge 1/q, b - d:foo4 <- merge 35, c - e:foo4 <- deep-copy d - f:address:foo3 <- get e, q:offset - g:address:foo2, z:boolean <- maybe-convert *f, q:variant - h:address:foo1 <- get *g, p:offset - y:address:number <- get *h, p:offset - 1:number/raw <- copy *y -] -+mem: storing 34 in location 1 - -:(scenario deep_copy_cycles) -container foo [ - p:number - q:address:foo -] -def main [ - local-scope - x:address:foo <- new foo:type - *x <- put *x, p:offset, 34 - *x <- put *x, q:offset, x # create a cycle - y:address:foo <- deep-copy x - 1:number/raw <- get *y, p:offset - y2:address:foo <- get *y, q:offset - stash y [vs] y2 - 2:boolean/raw <- equal y, y2 # is it still a cycle? - 3:boolean/raw <- equal x, y # is it the same cycle? -] -+mem: storing 34 in location 1 -# deep copy also contains a cycle -+mem: storing 1 in location 2 -# but it's a completely different (disjoint) cycle -+mem: storing 0 in location 3 diff --git a/073wait.cc b/073wait.cc new file mode 100644 index 00000000..584e88e3 --- /dev/null +++ b/073wait.cc @@ -0,0 +1,329 @@ +//: Routines can be put in a 'waiting' state, from which it will be ready to +//: run again when a specific memory location changes its value. This is mu's +//: basic technique for orchestrating the order in which different routines +//: operate. + +:(scenario wait_for_location) +def f1 [ + 1:number <- copy 0 + start-running f2 + 2:location <- copy 1/unsafe + wait-for-location 2:location + # now wait for f2 to run and modify location 1 before using its value + 3:number <- copy 1:number +] +def f2 [ + 1:number <- copy 34 +] +# if we got the synchronization wrong we'd be storing 0 in location 3 ++mem: storing 34 in location 3 + +//: define the new state that all routines can be in + +:(before "End routine States") +WAITING, +:(before "End routine Fields") +// only if state == WAITING +int waiting_on_location; +int old_value_of_waiting_location; +:(before "End routine Constructor") +waiting_on_location = old_value_of_waiting_location = 0; + +:(before "End Mu Test Teardown") +if (Passed && any_routines_waiting()) { + Passed = false; + raise << Current_scenario->name << ": deadlock!\n" << end(); +} +:(before "End Test Teardown") +if (Passed && any_routines_with_error()) { + Passed = false; + raise << "some routines died with errors\n" << end(); +} +:(code) +bool any_routines_waiting() { + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state == WAITING) + return true; + } + return false; +} + +//: primitive recipe to put routines in that state + +:(before "End Primitive Recipe Declarations") +WAIT_FOR_LOCATION, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "wait-for-location", WAIT_FOR_LOCATION); +:(before "End Primitive Recipe Checks") +case WAIT_FOR_LOCATION: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'wait-for-location' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_location(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "'wait-for-location' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + } + break; +} +:(before "End Primitive Recipe Implementations") +case WAIT_FOR_LOCATION: { + int loc = ingredients.at(0).at(0); + Current_routine->state = WAITING; + Current_routine->waiting_on_location = loc; + Current_routine->old_value_of_waiting_location = get_or_insert(Memory, loc); + trace(9998, "run") << "waiting for location " << loc << " to change from " << no_scientific(get_or_insert(Memory, loc)) << end(); + break; +} + +//: scheduler tweak to get routines out of that state + +:(before "End Scheduler State Transitions") +for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state != WAITING) continue; + if (Routines.at(i)->waiting_on_location && + get_or_insert(Memory, Routines.at(i)->waiting_on_location) != Routines.at(i)->old_value_of_waiting_location) { + trace(9999, "schedule") << "waking up routine\n" << end(); + Routines.at(i)->state = RUNNING; + Routines.at(i)->waiting_on_location = Routines.at(i)->old_value_of_waiting_location = 0; + } +} + +//: primitive to help compute locations to wait for +//: only supports elements inside containers, no arrays or containers within +//: containers yet. + +:(scenario get_location) +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 15:location <- get-location 12:point, 1:offset +] ++mem: storing 13 in location 15 + +:(before "End Primitive Recipe Declarations") +GET_LOCATION, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "get-location", GET_LOCATION); +:(before "End Primitive Recipe Checks") +case GET_LOCATION: { + if (SIZE(inst.ingredients) != 2) { + raise << maybe(get(Recipe, r).name) << "'get-location' expects exactly 2 ingredients in '" << inst.original_string << "'\n" << end(); + break; + } + reagent/*copy*/ base = inst.ingredients.at(0); + if (!canonize_type(base)) break; + if (!base.type || !base.type->value || !contains_key(Type, base.type->value) || get(Type, base.type->value).kind != CONTAINER) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'get-location' should be a container, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + type_ordinal base_type = base.type->value; + const reagent& offset = inst.ingredients.at(1); + if (!is_literal(offset) || !is_mu_scalar(offset)) { + raise << maybe(get(Recipe, r).name) << "second ingredient of 'get-location' should have type 'offset', but got '" << inst.ingredients.at(1).original_string << "'\n" << end(); + break; + } + int offset_value = 0; + if (is_integer(offset.name)) { // later layers permit non-integer offsets + offset_value = to_integer(offset.name); + if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { + raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for '" << get(Type, base_type).name << "'\n" << end(); + break; + } + } + else { + offset_value = offset.value; + } + if (inst.products.empty()) break; + if (!is_mu_location(inst.products.at(0))) { + raise << maybe(get(Recipe, r).name) << "'get-location " << base.original_string << ", " << offset.original_string << "' should write to type location but '" << inst.products.at(0).name << "' has type '" << names_to_string_without_quotes(inst.products.at(0).type) << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case GET_LOCATION: { + reagent/*copy*/ base = current_instruction().ingredients.at(0); + canonize(base); + int base_address = base.value; + if (base_address == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + type_ordinal base_type = base.type->value; + int offset = ingredients.at(1).at(0); + if (offset < 0 || offset >= SIZE(get(Type, base_type).elements)) break; // copied from Check above + int result = base_address; + for (int i = 0; i < offset; ++i) + result += size_of(element_type(base.type, i)); + trace(9998, "run") << "address to copy is " << result << end(); + products.resize(1); + products.at(0).push_back(result); + break; +} + +:(code) +bool is_mu_location(reagent/*copy*/ x) { + if (!canonize_type(x)) return false; + if (!x.type) return false; + if (x.type->right) return false; + return x.type->value == get(Type_ordinal, "location"); +} + +:(scenario get_location_out_of_bounds) +% Hide_errors = true; +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + get-location 12:point-number/raw, 2:offset # point-number occupies 3 locations but has only 2 fields; out of bounds +] ++error: main: invalid offset 2 for 'point-number' + +:(scenario get_location_out_of_bounds_2) +% Hide_errors = true; +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + get-location 12:point-number/raw, -1:offset +] ++error: main: invalid offset -1 for 'point-number' + +:(scenario get_location_product_type_mismatch) +% Hide_errors = true; +container boolbool [ + x:boolean + y:boolean +] +def main [ + 12:boolean <- copy 1 + 13:boolean <- copy 0 + 15:boolean <- get-location 12:boolbool, 1:offset +] ++error: main: 'get-location 12:boolbool, 1:offset' should write to type location but '15' has type 'boolean' + +:(scenario get_location_indirect) +# 'get-location' can read from container address +def main [ + 1:number <- copy 10 + # 10 reserved for refcount + 11:number <- copy 34 + 12:number <- copy 35 + 4:location <- get-location 1:address:point/lookup, 0:offset +] ++mem: storing 11 in location 4 + +:(scenario get_location_indirect_2) +def main [ + 1:number <- copy 10 + # 10 reserved for refcount + 11:number <- copy 34 + 12:number <- copy 35 + 4:address:number <- copy 20/unsafe + 4:address:location/lookup <- get-location 1:address:point/lookup, 0:offset +] ++mem: storing 11 in location 21 + +//: also allow waiting on a routine to stop running + +:(scenario wait_for_routine) +def f1 [ + 1:number <- copy 0 + 12:number/routine <- start-running f2 + wait-for-routine 12:number/routine + # now wait for f2 to run and modify location 1 before using its value + 3:number <- copy 1:number +] +def f2 [ + 1:number <- copy 34 +] ++schedule: f1 ++run: waiting for routine 2 ++schedule: f2 ++schedule: waking up routine 1 ++schedule: f1 +# if we got the synchronization wrong we'd be storing 0 in location 3 ++mem: storing 34 in location 3 + +:(before "End routine Fields") +// only if state == WAITING +int waiting_on_routine; +:(before "End routine Constructor") +waiting_on_routine = 0; + +:(before "End Primitive Recipe Declarations") +WAIT_FOR_ROUTINE, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE); +:(before "End Primitive Recipe Checks") +case WAIT_FOR_ROUTINE: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case WAIT_FOR_ROUTINE: { + if (ingredients.at(0).at(0) == Current_routine->id) { + raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + Current_routine->state = WAITING; + Current_routine->waiting_on_routine = ingredients.at(0).at(0); + trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end(); + break; +} + +:(before "End Scheduler State Transitions") +// Wake up any routines waiting for other routines to go to sleep. +// Important: this must come after the scheduler loop above giving routines +// waiting for locations to change a chance to wake up. +for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state != WAITING) continue; + if (!Routines.at(i)->waiting_on_routine) continue; + int id = Routines.at(i)->waiting_on_routine; + assert(id != Routines.at(i)->id); // routine can't wait on itself + for (int j = 0; j < SIZE(Routines); ++j) { + if (Routines.at(j)->id == id && Routines.at(j)->state != RUNNING) { + trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end(); + Routines.at(i)->state = RUNNING; + Routines.at(i)->waiting_on_routine = 0; + } + } +} + +:(before "End Primitive Recipe Declarations") +SWITCH, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "switch", SWITCH); +:(before "End Primitive Recipe Checks") +case SWITCH: { + break; +} +:(before "End Primitive Recipe Implementations") +case SWITCH: { + int id = some_other_running_routine(); + if (id) { + assert(id != Current_routine->id); + Current_routine->state = WAITING; + Current_routine->waiting_on_routine = id; + } + break; +} + +:(code) +int some_other_running_routine() { + for (int i = 0; i < SIZE(Routines); ++i) { + if (i == Current_routine_index) continue; + assert(Routines.at(i) != Current_routine); + assert(Routines.at(i)->id != Current_routine->id); + if (Routines.at(i)->state == RUNNING) + return Routines.at(i)->id; + } + return 0; +} diff --git a/074channel.mu b/074channel.mu deleted file mode 100644 index e018db2f..00000000 --- a/074channel.mu +++ /dev/null @@ -1,452 +0,0 @@ -# Mu synchronizes using channels rather than locks, like Erlang and Go. -# -# The two ends of a channel will usually belong to different routines, but -# each end should (currently) only be used by a single one. Don't try to read -# from or write to it from multiple routines at once. -# -# Key properties of channels: -# -# a) Writing to a full channel or reading from an empty one will put the -# current routine in 'waiting' state until the operation can be completed. -# -# b) Writing to a channel implicitly performs a deep copy, to prevent -# addresses from being shared between routines, thereby causing race -# conditions. - -scenario channel [ - run [ - local-scope - source:address:source:number, sink:address:sink:number <- new-channel 3/capacity - sink <- write sink, 34 - 10:number/raw, 11:boolean/raw, source <- read source - ] - memory-should-contain [ - 10 <- 34 - 11 <- 0 # read was successful - ] -] - -container channel:_elem [ - # To avoid locking, writer and reader will never write to the same location. - # So channels will include fields in pairs, one for the writer and one for the - # reader. - first-full:number # for write - first-free:number # for read - # A circular buffer contains values from index first-full up to (but not - # including) index first-empty. The reader always modifies it at first-full, - # while the writer always modifies it at first-empty. - data:address:array:_elem -] - -# Since channels have two ends, and since it's an error to use either end from -# multiple routines, let's distinguish the ends. - -container source:_elem [ - chan:address:channel:_elem -] - -container sink:_elem [ - chan:address:channel:_elem -] - -def new-channel capacity:number -> in:address:source:_elem, out:address:sink:_elem [ - local-scope - load-ingredients - result:address:channel:_elem <- new {(channel _elem): type} - *result <- put *result, first-full:offset, 0 - *result <- put *result, first-free:offset, 0 - capacity <- add capacity, 1 # unused slot for 'full?' below - data:address:array:_elem <- new _elem:type, capacity - *result <- put *result, data:offset, data - in <- new {(source _elem): type} - *in <- put *in, chan:offset, result - out <- new {(sink _elem): type} - *out <- put *out, chan:offset, result -] - -def write out:address:sink:_elem, val:_elem -> out:address:sink:_elem [ - local-scope - load-ingredients - chan:address:channel:_elem <- get *out, chan:offset - - { - # block if chan is full - full:boolean <- channel-full? chan - break-unless full - full-address:location <- get-location *chan, first-full:offset - wait-for-location full-address - } - # store a deep copy of val - circular-buffer:address:array:_elem <- get *chan, data:offset - free:number <- get *chan, first-free:offset - val-copy:_elem <- deep-copy val # on this instruction rests all Mu's concurrency-safety - *circular-buffer <- put-index *circular-buffer, free, val-copy - # mark its slot as filled - free <- add free, 1 - { - # wrap free around to 0 if necessary - len:number <- length *circular-buffer - at-end?:boolean <- greater-or-equal free, len - break-unless at-end? - free <- copy 0 - } - # write back - *chan <- put *chan, first-free:offset, free -] - -def read in:address:source:_elem -> result:_elem, fail?:boolean, in:address:source:_elem [ - local-scope - load-ingredients - fail? <- copy 0/false # default status - chan:address:channel:_elem <- get *in, chan:offset - { - # block if chan is empty - empty?:boolean <- channel-empty? chan - break-unless empty? - - free-address:location <- get-location *chan, first-free:offset - wait-for-location free-address - } - # pull result off - full:number <- get *chan, first-full:offset - circular-buffer:address:array:_elem <- get *chan, data:offset - result <- index *circular-buffer, full - # clear the slot - empty:address:_elem <- new _elem:type - *circular-buffer <- put-index *circular-buffer, full, *empty - # mark its slot as empty - full <- add full, 1 - { - # wrap full around to 0 if necessary - len:number <- length *circular-buffer - at-end?:boolean <- greater-or-equal full, len - break-unless at-end? - full <- copy 0 - } - # write back - *chan <- put *chan, first-full:offset, full -] - -def clear in:address:source:_elem -> in:address:source:_elem [ - local-scope - load-ingredients - chan:address:channel:_elem <- get *in, chan:offset - { - empty?:boolean <- channel-empty? chan - break-if empty? - _, _, in <- read in - } -] - -scenario channel-initialization [ - run [ - local-scope - source:address:source:number <- new-channel 3/capacity - chan:address:channel:number <- get *source, chan:offset - 10:number/raw <- get *chan, first-full:offset - 11:number/raw <- get *chan, first-free:offset - ] - memory-should-contain [ - 10 <- 0 # first-full - 11 <- 0 # first-free - ] -] - -scenario channel-write-increments-free [ - run [ - local-scope - _, sink:address:sink:number <- new-channel 3/capacity - sink <- write sink, 34 - chan:address:channel:number <- get *sink, chan:offset - 10:number/raw <- get *chan, first-full:offset - 11:number/raw <- get *chan, first-free:offset - ] - memory-should-contain [ - 10 <- 0 # first-full - 11 <- 1 # first-free - ] -] - -scenario channel-read-increments-full [ - run [ - local-scope - source:address:source:number, sink:address:sink:number <- new-channel 3/capacity - sink <- write sink, 34 - _, _, source <- read source - chan:address:channel:number <- get *source, chan:offset - 10:number/raw <- get *chan, first-full:offset - 11:number/raw <- get *chan, first-free:offset - ] - memory-should-contain [ - 10 <- 1 # first-full - 11 <- 1 # first-free - ] -] - -scenario channel-wrap [ - run [ - local-scope - # channel with just 1 slot - source:address:source:number, sink:address:sink:number <- new-channel 1/capacity - chan:address:channel:number <- get *source, chan:offset - # write and read a value - sink <- write sink, 34 - _, _, source <- read source - # first-free will now be 1 - 10:number/raw <- get *chan, first-free:offset - 11:number/raw <- get *chan, first-free:offset - # write second value, verify that first-free wraps - sink <- write sink, 34 - 20:number/raw <- get *chan, first-free:offset - # read second value, verify that first-full wraps - _, _, source <- read source - 30:number/raw <- get *chan, first-full:offset - ] - memory-should-contain [ - 10 <- 1 # first-free after first write - 11 <- 1 # first-full after first read - 20 <- 0 # first-free after second write, wrapped - 30 <- 0 # first-full after second read, wrapped - ] -] - -scenario channel-new-empty-not-full [ - run [ - local-scope - source:address:source:number <- new-channel 3/capacity - chan:address:channel:number <- get *source, chan:offset - 10:boolean/raw <- channel-empty? chan - 11:boolean/raw <- channel-full? chan - ] - memory-should-contain [ - 10 <- 1 # empty? - 11 <- 0 # full? - ] -] - -scenario channel-write-not-empty [ - run [ - source:address:source:number, sink:address:sink:number <- new-channel 3/capacity - chan:address:channel:number <- get *source, chan:offset - sink <- write sink, 34 - 10:boolean/raw <- channel-empty? chan - 11:boolean/raw <- channel-full? chan - ] - memory-should-contain [ - 10 <- 0 # empty? - 11 <- 0 # full? - ] -] - -scenario channel-write-full [ - run [ - local-scope - source:address:source:number, sink:address:sink:number <- new-channel 1/capacity - chan:address:channel:number <- get *source, chan:offset - sink <- write sink, 34 - 10:boolean/raw <- channel-empty? chan - 11:boolean/raw <- channel-full? chan - ] - memory-should-contain [ - 10 <- 0 # empty? - 11 <- 1 # full? - ] -] - -scenario channel-read-not-full [ - run [ - local-scope - source:address:source:number, sink:address:sink:number <- new-channel 1/capacity - chan:address:channel:number <- get *source, chan:offset - sink <- write sink, 34 - _, _, source <- read source - 10:boolean/raw <- channel-empty? chan - 11:boolean/raw <- channel-full? chan - ] - memory-should-contain [ - 10 <- 1 # empty? - 11 <- 0 # full? - ] -] - -## cancelling channels - -# every channel comes with a boolean signifying if it's been closed -# initially this boolean is false -container channel:_elem [ - closed?:boolean -] - -# a channel can be closed from either the source or the sink -# both routines can modify the 'closed?' bit, but they can only ever set it, so this is a benign race -def close x:address:source:_elem -> x:address:source:_elem [ - local-scope - load-ingredients - chan:address:channel:_elem <- get *x, chan:offset - *chan <- put *chan, closed?:offset, 1/true -] -def close x:address:sink:_elem -> x:address:sink:_elem [ - local-scope - load-ingredients - chan:address:channel:_elem <- get *x, chan:offset - *chan <- put *chan, closed?:offset, 1/true -] - -# once a channel is closed from one side, no further operations are expected from that side -# if a channel is closed for reading, -# no further writes will be let through -# if a channel is closed for writing, -# future reads continue until the channel empties, -# then the channel is also closed for reading -after [ - closed?:boolean <- get *chan, closed?:offset - return-if closed? -] - -after [ - closed?:boolean <- get *chan, closed?:offset - { - break-unless closed? - empty-result:address:_elem <- new _elem:type - return *empty-result, 1/true - } -] - -## helpers - -# An empty channel has first-empty and first-full both at the same value. -def channel-empty? chan:address:channel:_elem -> result:boolean [ - local-scope - load-ingredients - # return chan.first-full == chan.first-free - full:number <- get *chan, first-full:offset - free:number <- get *chan, first-free:offset - result <- equal full, free -] - -# A full channel has first-empty just before first-full, wasting one slot. -# (Other alternatives: https://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction) -def channel-full? chan:address:channel:_elem -> result:boolean [ - local-scope - load-ingredients - # tmp = chan.first-free + 1 - tmp:number <- get *chan, first-free:offset - tmp <- add tmp, 1 - { - # if tmp == chan.capacity, tmp = 0 - len:number <- capacity chan - at-end?:boolean <- greater-or-equal tmp, len - break-unless at-end? - tmp <- copy 0 - } - # return chan.first-full == tmp - full:number <- get *chan, first-full:offset - result <- equal full, tmp -] - -def capacity chan:address:channel:_elem -> result:number [ - local-scope - load-ingredients - q:address:array:_elem <- get *chan, data:offset - result <- length *q -] - -# helper for channels of characters in particular -def buffer-lines in:address:source:character, buffered-out:address:sink:character -> buffered-out:address:sink:character, in:address:source:character [ - local-scope - load-ingredients - # repeat forever - eof?:boolean <- copy 0/false - { - line:address:buffer <- new-buffer 30 - # read characters from 'in' until newline, copy into line - { - +next-character - c:character, eof?:boolean, in <- read in - break-if eof? - # drop a character on backspace - { - # special-case: if it's a backspace - backspace?:boolean <- equal c, 8 - break-unless backspace? - # drop previous character - { - buffer-length:number <- get *line, length:offset - buffer-empty?:boolean <- equal buffer-length, 0 - break-if buffer-empty? - buffer-length <- subtract buffer-length, 1 - *line <- put *line, length:offset, buffer-length - } - # and don't append this one - loop +next-character:label - } - # append anything else - line <- append line, c - line-done?:boolean <- equal c, 10/newline - break-if line-done? - loop - } - # copy line into 'buffered-out' - i:number <- copy 0 - line-contents:address:array:character <- get *line, data:offset - max:number <- get *line, length:offset - { - done?:boolean <- greater-or-equal i, max - break-if done? - c:character <- index *line-contents, i - buffered-out <- write buffered-out, c - i <- add i, 1 - loop - } - { - break-unless eof? - buffered-out <- close buffered-out - return - } - loop - } -] - -scenario buffer-lines-blocks-until-newline [ - run [ - local-scope - source:address:source:character, sink:address:sink:character <- new-channel 10/capacity - _, buffered-stdin:address:sink:character/buffered-stdin <- new-channel 10/capacity - buffered-chan:address:channel:character <- get *buffered-stdin, chan:offset - empty?:boolean <- channel-empty? buffered-chan - assert empty?, [ -F buffer-lines-blocks-until-newline: channel should be empty after init] - # buffer stdin into buffered-stdin, try to read from buffered-stdin - buffer-routine:number <- start-running buffer-lines, source, buffered-stdin - wait-for-routine buffer-routine - empty? <- channel-empty? buffered-chan - assert empty?:boolean, [ -F buffer-lines-blocks-until-newline: channel should be empty after buffer-lines bring-up] - # write 'a' - sink <- write sink, 97/a - restart buffer-routine - wait-for-routine buffer-routine - empty? <- channel-empty? buffered-chan - assert empty?:boolean, [ -F buffer-lines-blocks-until-newline: channel should be empty after writing 'a'] - # write 'b' - sink <- write sink, 98/b - restart buffer-routine - wait-for-routine buffer-routine - empty? <- channel-empty? buffered-chan - assert empty?:boolean, [ -F buffer-lines-blocks-until-newline: channel should be empty after writing 'b'] - # write newline - sink <- write sink, 10/newline - restart buffer-routine - wait-for-routine buffer-routine - empty? <- channel-empty? buffered-chan - data-emitted?:boolean <- not empty? - assert data-emitted?, [ -F buffer-lines-blocks-until-newline: channel should contain data after writing newline] - trace 1, [test], [reached end] - ] - trace-should-contain [ - test: reached end - ] -] diff --git a/074deep_copy.cc b/074deep_copy.cc new file mode 100644 index 00000000..59f71286 --- /dev/null +++ b/074deep_copy.cc @@ -0,0 +1,387 @@ +// To recursively copy containers and any addresses they contain, use +// 'deep-copy'. +// +// Invariant: After a deep-copy its ingredient and result will point to no +// common addresses. +// Implications: Refcounts of all data pointed to by the original ingredient +// will remain unchanged. Refcounts of all data pointed to by the (newly +// created) result will be 1, in the absence of cycles. +// +// We do handle cycles in the ingredient, however. All cycles are translated +// to new cycles in the product. + +:(scenario deep_copy_number) +def main [ + local-scope + x:number <- copy 34 + y:number <- deep-copy x + 10:boolean/raw <- equal x, y +] +# non-address primitives are identical ++mem: storing 1 in location 10 + +:(scenario deep_copy_container_without_address) +container foo [ + x:number + y:number +] +def main [ + local-scope + a:foo <- merge 34, 35 + b:foo <- deep-copy a + 10:boolean/raw <- equal a, b +] +# containers are identical as long as they don't contain addresses ++mem: storing 1 in location 10 + +:(scenario deep_copy_address) +% Memory_allocated_until = 200; +def main [ + # avoid all memory allocations except the implicit ones inside deep-copy, so + # that the result is deterministic + 1:address:number <- copy 100/unsafe # pretend allocation + *1:address:number <- copy 34 + 2:address:number <- deep-copy 1:address:number + 10:boolean <- equal 1:address:number, 2:address:number + 11:boolean <- equal *1:address:number, *2:address:number + 2:address:number <- copy 0 +] +# the result of deep-copy is a new address ++mem: storing 0 in location 10 +# however, the contents are identical ++mem: storing 1 in location 11 +# the result of deep-copy gets a refcount of 1 +# (its address 202 = 200 base + 2 for temporary space inside deep-copy) ++run: {2: ("address" "number")} <- copy {0: "literal"} ++mem: decrementing refcount of 202: 1 -> 0 ++abandon: saving 202 in free-list of size 2 + +:(scenario deep_copy_address_to_container) +% Memory_allocated_until = 200; +def main [ + # avoid all memory allocations except the implicit ones inside deep-copy, so + # that the result is deterministic + 1:address:point <- copy 100/unsafe # pretend allocation + *1:address:point <- merge 34, 35 + 2:address:point <- deep-copy 1:address:point + 10:boolean <- equal 1:address:point, 2:address:point + 11:boolean <- equal *1:address:point, *2:address:point +] +# the result of deep-copy is a new address ++mem: storing 0 in location 10 +# however, the contents are identical ++mem: storing 1 in location 11 + +:(scenario deep_copy_address_to_address) +% Memory_allocated_until = 200; +def main [ + # avoid all memory allocations except the implicit ones inside deep-copy, so + # that the result is deterministic + 1:address:address:number <- copy 100/unsafe # pretend allocation + *1:address:address:number <- copy 150/unsafe + **1:address:address:number <- copy 34 + 2:address:address:number <- deep-copy 1:address:address:number + 10:boolean <- equal 1:address:address:number, 2:address:address:number + 11:boolean <- equal *1:address:address:number, *2:address:address:number + 12:boolean <- equal **1:address:address:number, **2:address:address:number +] +# the result of deep-copy is a new address ++mem: storing 0 in location 10 +# any addresses in it or pointed to it are also new ++mem: storing 0 in location 11 +# however, the non-address contents are identical ++mem: storing 1 in location 12 + +:(scenario deep_copy_array) +% Memory_allocated_until = 200; +def main [ + # avoid all memory allocations except the implicit ones inside deep-copy, so + # that the result is deterministic + 100:number <- copy 1 # pretend refcount + 101:number <- copy 3 # pretend array length + 1:address:array:number <- copy 100/unsafe # pretend allocation + put-index *1:address:array:number, 0, 34 + put-index *1:address:array:number, 1, 35 + put-index *1:address:array:number, 2, 36 + stash [old:], *1:address:array:number + 2:address:array:number <- deep-copy 1:address:array:number + stash 2:address:array:number + stash [new:], *2:address:array:number + 10:boolean <- equal 1:address:array:number, 2:address:array:number + 11:boolean <- equal *1:address:array:number, *2:address:array:number +] ++app: old: 3 34 35 36 ++app: new: 3 34 35 36 +# the result of deep-copy is a new address ++mem: storing 0 in location 10 +# however, the contents are identical ++mem: storing 1 in location 11 + +:(scenario deep_copy_container_with_address) +container foo [ + x:number + y:address:number +] +def main [ + local-scope + y0:address:number <- new number:type + *y0 <- copy 35 + a:foo <- merge 34, y0 + b:foo <- deep-copy a + 10:boolean/raw <- equal a, b + y1:address:number <- get b, y:offset + 11:boolean/raw <- equal y0, y1 + 12:number/raw <- copy *y1 +] +# containers containing addresses are not identical to their deep copies ++mem: storing 0 in location 10 +# the addresses they contain are not identical either ++mem: storing 0 in location 11 ++mem: storing 35 in location 12 + +:(scenario deep_copy_exclusive_container_with_address) +exclusive-container foo [ + x:number + y:address:number +] +def main [ + local-scope + y0:address:number <- new number:type + *y0 <- copy 34 + a:foo <- merge 1/y, y0 + b:foo <- deep-copy a + 10:boolean/raw <- equal a, b + y1:address:number, z:boolean <- maybe-convert b, y:variant + 11:boolean/raw <- equal y0, y1 + 12:number/raw <- copy *y1 +] +# exclusive containers containing addresses are not identical to their deep copies ++mem: storing 0 in location 10 +# the addresses they contain are not identical either ++mem: storing 0 in location 11 ++mem: storing 34 in location 12 + +:(scenario deep_copy_exclusive_container_with_container_with_address) +exclusive-container foo [ + x:number + y:bar # inline +] +container bar [ + x:address:number +] +def main [ + local-scope + y0:address:number <- new number:type + *y0 <- copy 34 + a:bar <- merge y0 + b:foo <- merge 1/y, a + c:foo <- deep-copy b + 10:boolean/raw <- equal b, c + d:bar, z:boolean <- maybe-convert c, y:variant + y1:address:number <- get d, x:offset + 11:boolean/raw <- equal y0, y1 + 12:number/raw <- copy *y1 +] +# exclusive containers containing addresses are not identical to their deep copies ++mem: storing 0 in location 10 +# sub-containers containing addresses are not identical either ++mem: storing 0 in location 11 ++mem: storing 34 in location 12 + +:(before "End Primitive Recipe Declarations") +DEEP_COPY, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "deep-copy", DEEP_COPY); +:(before "End Primitive Recipe Checks") +case DEEP_COPY: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); + break; + } + if (SIZE(inst.products) != 1) { + raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); + break; + } + if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) { + raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << inst.original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case DEEP_COPY: { + const reagent& input = current_instruction().ingredients.at(0); + // allocate a tiny bit of temporary space for deep_copy() + trace(9991, "run") << "deep-copy: allocating space for temporary" << end(); + reagent tmp("tmp:address:number"); + tmp.value = allocate(1); + products.push_back(deep_copy(input, tmp)); + // reclaim Mu memory allocated for tmp + trace(9991, "run") << "deep-copy: reclaiming temporary" << end(); + abandon(tmp.value, tmp.type->right, payload_size(tmp)); + // reclaim host memory allocated for tmp.type when tmp goes out of scope + break; +} + +:(code) +vector deep_copy(const reagent& in, const reagent& tmp) { + map addresses_copied; + return deep_copy(in, addresses_copied, tmp); +} + +vector deep_copy(reagent/*copy*/ in, map& addresses_copied, const reagent& tmp) { + canonize(in); + vector result; + if (is_mu_address(in)) + result.push_back(deep_copy_address(in, addresses_copied, tmp)); + else + deep_copy(in, addresses_copied, tmp, result); + return result; +} + +// deep-copy an address and return a new address +int deep_copy_address(const reagent& canonized_in, map& addresses_copied, const reagent& tmp) { + if (canonized_in.value == 0) return 0; + int in_address = payload_address(canonized_in); + trace(9991, "run") << "deep-copy: copying address " << in_address << end(); + if (contains_key(addresses_copied, in_address)) { + int out = get(addresses_copied, in_address); + trace(9991, "run") << "deep-copy: copy already exists: " << out << end(); + return out; + } + int out = allocate(payload_size(canonized_in)); + trace(9991, "run") << "deep-copy: new address is " << out << end(); + put(addresses_copied, in_address, out); + reagent/*copy*/ payload = canonized_in; + payload.properties.push_back(pair("lookup", NULL)); + trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end(); + vector data = deep_copy(payload, addresses_copied, tmp); + trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end(); + // HACK: write_memory interface isn't ideal for this situation; we need + // a temporary location to help copy the payload. + trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end(); + put(Memory, tmp.value, out); + payload.value = tmp.value; // now modified for output + vector old_data = read_memory(payload); + trace(9991, "run") << "deep-copy: really writing to " << payload.value << ' ' << to_string(payload) << " (old value " << to_string(old_data) << " new value " << to_string(data) << ")" << end(); + write_memory(payload, data, -1); + trace(9991, "run") << "deep-copy: output is " << to_string(data) << end(); + return out; +} + +// deep-copy a non-address and return a vector of locations +void deep_copy(const reagent& canonized_in, map& addresses_copied, const reagent& tmp, vector& out) { + assert(!is_mu_address(canonized_in)); + vector data = read_memory(canonized_in); + out.insert(out.end(), data.begin(), data.end()); + if (!contains_key(Container_metadata, canonized_in.type)) return; + trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end(); + const container_metadata& metadata = get(Container_metadata, canonized_in.type); + for (map, set >::const_iterator p = metadata.address.begin(); p != metadata.address.end(); ++p) { + if (!all_match(data, p->first)) continue; + for (set::const_iterator info = p->second.begin(); info != p->second.end(); ++info) { + // construct a fake reagent that reads directly from the appropriate + // field of the container + reagent curr; + curr.type = new type_tree("address", new type_tree(*info->payload_type)); + curr.set_value(canonized_in.value + info->offset); + curr.properties.push_back(pair("raw", NULL)); + trace(9991, "run") << "deep-copy: copying address " << curr.value << end(); + out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp); + } + } +} + +int payload_address(reagent/*copy*/ x) { + x.properties.push_back(pair("lookup", NULL)); + canonize(x); + return x.value; +} + +//: moar tests, just because I can't believe it all works + +:(scenario deep_copy_stress_test_1) +container foo1 [ + p:address:number +] +container foo2 [ + p:address:foo1 +] +exclusive-container foo3 [ + p:address:foo1 + q:address:foo2 +] +def main [ + local-scope + x:address:number <- new number:type + *x <- copy 34 + a:address:foo1 <- new foo1:type + *a <- merge x + b:address:foo2 <- new foo2:type + *b <- merge a + c:foo3 <- merge 1/q, b + d:foo3 <- deep-copy c + e:address:foo2, z:boolean <- maybe-convert d, q:variant + f:address:foo1 <- get *e, p:offset + g:address:number <- get *f, p:offset + 1:number/raw <- copy *g +] ++mem: storing 34 in location 1 + +:(scenario deep_copy_stress_test_2) +container foo1 [ + p:address:number +] +container foo2 [ + p:address:foo1 +] +exclusive-container foo3 [ + p:address:foo1 + q:address:foo2 +] +container foo4 [ + p:number + q:address:foo3 +] +def main [ + local-scope + x:address:number <- new number:type + *x <- copy 34 + a:address:foo1 <- new foo1:type + *a <- merge x + b:address:foo2 <- new foo2:type + *b <- merge a + c:address:foo3 <- new foo3:type + *c <- merge 1/q, b + d:foo4 <- merge 35, c + e:foo4 <- deep-copy d + f:address:foo3 <- get e, q:offset + g:address:foo2, z:boolean <- maybe-convert *f, q:variant + h:address:foo1 <- get *g, p:offset + y:address:number <- get *h, p:offset + 1:number/raw <- copy *y +] ++mem: storing 34 in location 1 + +:(scenario deep_copy_cycles) +container foo [ + p:number + q:address:foo +] +def main [ + local-scope + x:address:foo <- new foo:type + *x <- put *x, p:offset, 34 + *x <- put *x, q:offset, x # create a cycle + y:address:foo <- deep-copy x + 1:number/raw <- get *y, p:offset + y2:address:foo <- get *y, q:offset + stash y [vs] y2 + 2:boolean/raw <- equal y, y2 # is it still a cycle? + 3:boolean/raw <- equal x, y # is it the same cycle? +] ++mem: storing 34 in location 1 +# deep copy also contains a cycle ++mem: storing 1 in location 2 +# but it's a completely different (disjoint) cycle ++mem: storing 0 in location 3 diff --git a/075channel.mu b/075channel.mu new file mode 100644 index 00000000..e018db2f --- /dev/null +++ b/075channel.mu @@ -0,0 +1,452 @@ +# Mu synchronizes using channels rather than locks, like Erlang and Go. +# +# The two ends of a channel will usually belong to different routines, but +# each end should (currently) only be used by a single one. Don't try to read +# from or write to it from multiple routines at once. +# +# Key properties of channels: +# +# a) Writing to a full channel or reading from an empty one will put the +# current routine in 'waiting' state until the operation can be completed. +# +# b) Writing to a channel implicitly performs a deep copy, to prevent +# addresses from being shared between routines, thereby causing race +# conditions. + +scenario channel [ + run [ + local-scope + source:address:source:number, sink:address:sink:number <- new-channel 3/capacity + sink <- write sink, 34 + 10:number/raw, 11:boolean/raw, source <- read source + ] + memory-should-contain [ + 10 <- 34 + 11 <- 0 # read was successful + ] +] + +container channel:_elem [ + # To avoid locking, writer and reader will never write to the same location. + # So channels will include fields in pairs, one for the writer and one for the + # reader. + first-full:number # for write + first-free:number # for read + # A circular buffer contains values from index first-full up to (but not + # including) index first-empty. The reader always modifies it at first-full, + # while the writer always modifies it at first-empty. + data:address:array:_elem +] + +# Since channels have two ends, and since it's an error to use either end from +# multiple routines, let's distinguish the ends. + +container source:_elem [ + chan:address:channel:_elem +] + +container sink:_elem [ + chan:address:channel:_elem +] + +def new-channel capacity:number -> in:address:source:_elem, out:address:sink:_elem [ + local-scope + load-ingredients + result:address:channel:_elem <- new {(channel _elem): type} + *result <- put *result, first-full:offset, 0 + *result <- put *result, first-free:offset, 0 + capacity <- add capacity, 1 # unused slot for 'full?' below + data:address:array:_elem <- new _elem:type, capacity + *result <- put *result, data:offset, data + in <- new {(source _elem): type} + *in <- put *in, chan:offset, result + out <- new {(sink _elem): type} + *out <- put *out, chan:offset, result +] + +def write out:address:sink:_elem, val:_elem -> out:address:sink:_elem [ + local-scope + load-ingredients + chan:address:channel:_elem <- get *out, chan:offset + + { + # block if chan is full + full:boolean <- channel-full? chan + break-unless full + full-address:location <- get-location *chan, first-full:offset + wait-for-location full-address + } + # store a deep copy of val + circular-buffer:address:array:_elem <- get *chan, data:offset + free:number <- get *chan, first-free:offset + val-copy:_elem <- deep-copy val # on this instruction rests all Mu's concurrency-safety + *circular-buffer <- put-index *circular-buffer, free, val-copy + # mark its slot as filled + free <- add free, 1 + { + # wrap free around to 0 if necessary + len:number <- length *circular-buffer + at-end?:boolean <- greater-or-equal free, len + break-unless at-end? + free <- copy 0 + } + # write back + *chan <- put *chan, first-free:offset, free +] + +def read in:address:source:_elem -> result:_elem, fail?:boolean, in:address:source:_elem [ + local-scope + load-ingredients + fail? <- copy 0/false # default status + chan:address:channel:_elem <- get *in, chan:offset + { + # block if chan is empty + empty?:boolean <- channel-empty? chan + break-unless empty? + + free-address:location <- get-location *chan, first-free:offset + wait-for-location free-address + } + # pull result off + full:number <- get *chan, first-full:offset + circular-buffer:address:array:_elem <- get *chan, data:offset + result <- index *circular-buffer, full + # clear the slot + empty:address:_elem <- new _elem:type + *circular-buffer <- put-index *circular-buffer, full, *empty + # mark its slot as empty + full <- add full, 1 + { + # wrap full around to 0 if necessary + len:number <- length *circular-buffer + at-end?:boolean <- greater-or-equal full, len + break-unless at-end? + full <- copy 0 + } + # write back + *chan <- put *chan, first-full:offset, full +] + +def clear in:address:source:_elem -> in:address:source:_elem [ + local-scope + load-ingredients + chan:address:channel:_elem <- get *in, chan:offset + { + empty?:boolean <- channel-empty? chan + break-if empty? + _, _, in <- read in + } +] + +scenario channel-initialization [ + run [ + local-scope + source:address:source:number <- new-channel 3/capacity + chan:address:channel:number <- get *source, chan:offset + 10:number/raw <- get *chan, first-full:offset + 11:number/raw <- get *chan, first-free:offset + ] + memory-should-contain [ + 10 <- 0 # first-full + 11 <- 0 # first-free + ] +] + +scenario channel-write-increments-free [ + run [ + local-scope + _, sink:address:sink:number <- new-channel 3/capacity + sink <- write sink, 34 + chan:address:channel:number <- get *sink, chan:offset + 10:number/raw <- get *chan, first-full:offset + 11:number/raw <- get *chan, first-free:offset + ] + memory-should-contain [ + 10 <- 0 # first-full + 11 <- 1 # first-free + ] +] + +scenario channel-read-increments-full [ + run [ + local-scope + source:address:source:number, sink:address:sink:number <- new-channel 3/capacity + sink <- write sink, 34 + _, _, source <- read source + chan:address:channel:number <- get *source, chan:offset + 10:number/raw <- get *chan, first-full:offset + 11:number/raw <- get *chan, first-free:offset + ] + memory-should-contain [ + 10 <- 1 # first-full + 11 <- 1 # first-free + ] +] + +scenario channel-wrap [ + run [ + local-scope + # channel with just 1 slot + source:address:source:number, sink:address:sink:number <- new-channel 1/capacity + chan:address:channel:number <- get *source, chan:offset + # write and read a value + sink <- write sink, 34 + _, _, source <- read source + # first-free will now be 1 + 10:number/raw <- get *chan, first-free:offset + 11:number/raw <- get *chan, first-free:offset + # write second value, verify that first-free wraps + sink <- write sink, 34 + 20:number/raw <- get *chan, first-free:offset + # read second value, verify that first-full wraps + _, _, source <- read source + 30:number/raw <- get *chan, first-full:offset + ] + memory-should-contain [ + 10 <- 1 # first-free after first write + 11 <- 1 # first-full after first read + 20 <- 0 # first-free after second write, wrapped + 30 <- 0 # first-full after second read, wrapped + ] +] + +scenario channel-new-empty-not-full [ + run [ + local-scope + source:address:source:number <- new-channel 3/capacity + chan:address:channel:number <- get *source, chan:offset + 10:boolean/raw <- channel-empty? chan + 11:boolean/raw <- channel-full? chan + ] + memory-should-contain [ + 10 <- 1 # empty? + 11 <- 0 # full? + ] +] + +scenario channel-write-not-empty [ + run [ + source:address:source:number, sink:address:sink:number <- new-channel 3/capacity + chan:address:channel:number <- get *source, chan:offset + sink <- write sink, 34 + 10:boolean/raw <- channel-empty? chan + 11:boolean/raw <- channel-full? chan + ] + memory-should-contain [ + 10 <- 0 # empty? + 11 <- 0 # full? + ] +] + +scenario channel-write-full [ + run [ + local-scope + source:address:source:number, sink:address:sink:number <- new-channel 1/capacity + chan:address:channel:number <- get *source, chan:offset + sink <- write sink, 34 + 10:boolean/raw <- channel-empty? chan + 11:boolean/raw <- channel-full? chan + ] + memory-should-contain [ + 10 <- 0 # empty? + 11 <- 1 # full? + ] +] + +scenario channel-read-not-full [ + run [ + local-scope + source:address:source:number, sink:address:sink:number <- new-channel 1/capacity + chan:address:channel:number <- get *source, chan:offset + sink <- write sink, 34 + _, _, source <- read source + 10:boolean/raw <- channel-empty? chan + 11:boolean/raw <- channel-full? chan + ] + memory-should-contain [ + 10 <- 1 # empty? + 11 <- 0 # full? + ] +] + +## cancelling channels + +# every channel comes with a boolean signifying if it's been closed +# initially this boolean is false +container channel:_elem [ + closed?:boolean +] + +# a channel can be closed from either the source or the sink +# both routines can modify the 'closed?' bit, but they can only ever set it, so this is a benign race +def close x:address:source:_elem -> x:address:source:_elem [ + local-scope + load-ingredients + chan:address:channel:_elem <- get *x, chan:offset + *chan <- put *chan, closed?:offset, 1/true +] +def close x:address:sink:_elem -> x:address:sink:_elem [ + local-scope + load-ingredients + chan:address:channel:_elem <- get *x, chan:offset + *chan <- put *chan, closed?:offset, 1/true +] + +# once a channel is closed from one side, no further operations are expected from that side +# if a channel is closed for reading, +# no further writes will be let through +# if a channel is closed for writing, +# future reads continue until the channel empties, +# then the channel is also closed for reading +after [ + closed?:boolean <- get *chan, closed?:offset + return-if closed? +] + +after [ + closed?:boolean <- get *chan, closed?:offset + { + break-unless closed? + empty-result:address:_elem <- new _elem:type + return *empty-result, 1/true + } +] + +## helpers + +# An empty channel has first-empty and first-full both at the same value. +def channel-empty? chan:address:channel:_elem -> result:boolean [ + local-scope + load-ingredients + # return chan.first-full == chan.first-free + full:number <- get *chan, first-full:offset + free:number <- get *chan, first-free:offset + result <- equal full, free +] + +# A full channel has first-empty just before first-full, wasting one slot. +# (Other alternatives: https://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction) +def channel-full? chan:address:channel:_elem -> result:boolean [ + local-scope + load-ingredients + # tmp = chan.first-free + 1 + tmp:number <- get *chan, first-free:offset + tmp <- add tmp, 1 + { + # if tmp == chan.capacity, tmp = 0 + len:number <- capacity chan + at-end?:boolean <- greater-or-equal tmp, len + break-unless at-end? + tmp <- copy 0 + } + # return chan.first-full == tmp + full:number <- get *chan, first-full:offset + result <- equal full, tmp +] + +def capacity chan:address:channel:_elem -> result:number [ + local-scope + load-ingredients + q:address:array:_elem <- get *chan, data:offset + result <- length *q +] + +# helper for channels of characters in particular +def buffer-lines in:address:source:character, buffered-out:address:sink:character -> buffered-out:address:sink:character, in:address:source:character [ + local-scope + load-ingredients + # repeat forever + eof?:boolean <- copy 0/false + { + line:address:buffer <- new-buffer 30 + # read characters from 'in' until newline, copy into line + { + +next-character + c:character, eof?:boolean, in <- read in + break-if eof? + # drop a character on backspace + { + # special-case: if it's a backspace + backspace?:boolean <- equal c, 8 + break-unless backspace? + # drop previous character + { + buffer-length:number <- get *line, length:offset + buffer-empty?:boolean <- equal buffer-length, 0 + break-if buffer-empty? + buffer-length <- subtract buffer-length, 1 + *line <- put *line, length:offset, buffer-length + } + # and don't append this one + loop +next-character:label + } + # append anything else + line <- append line, c + line-done?:boolean <- equal c, 10/newline + break-if line-done? + loop + } + # copy line into 'buffered-out' + i:number <- copy 0 + line-contents:address:array:character <- get *line, data:offset + max:number <- get *line, length:offset + { + done?:boolean <- greater-or-equal i, max + break-if done? + c:character <- index *line-contents, i + buffered-out <- write buffered-out, c + i <- add i, 1 + loop + } + { + break-unless eof? + buffered-out <- close buffered-out + return + } + loop + } +] + +scenario buffer-lines-blocks-until-newline [ + run [ + local-scope + source:address:source:character, sink:address:sink:character <- new-channel 10/capacity + _, buffered-stdin:address:sink:character/buffered-stdin <- new-channel 10/capacity + buffered-chan:address:channel:character <- get *buffered-stdin, chan:offset + empty?:boolean <- channel-empty? buffered-chan + assert empty?, [ +F buffer-lines-blocks-until-newline: channel should be empty after init] + # buffer stdin into buffered-stdin, try to read from buffered-stdin + buffer-routine:number <- start-running buffer-lines, source, buffered-stdin + wait-for-routine buffer-routine + empty? <- channel-empty? buffered-chan + assert empty?:boolean, [ +F buffer-lines-blocks-until-newline: channel should be empty after buffer-lines bring-up] + # write 'a' + sink <- write sink, 97/a + restart buffer-routine + wait-for-routine buffer-routine + empty? <- channel-empty? buffered-chan + assert empty?:boolean, [ +F buffer-lines-blocks-until-newline: channel should be empty after writing 'a'] + # write 'b' + sink <- write sink, 98/b + restart buffer-routine + wait-for-routine buffer-routine + empty? <- channel-empty? buffered-chan + assert empty?:boolean, [ +F buffer-lines-blocks-until-newline: channel should be empty after writing 'b'] + # write newline + sink <- write sink, 10/newline + restart buffer-routine + wait-for-routine buffer-routine + empty? <- channel-empty? buffered-chan + data-emitted?:boolean <- not empty? + assert data-emitted?, [ +F buffer-lines-blocks-until-newline: channel should contain data after writing newline] + trace 1, [test], [reached end] + ] + trace-should-contain [ + test: reached end + ] +] -- cgit 1.4.1-2-gfad0