From 81a324bec3e992d6a979830c5bcae89ac7cdf40c Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Wed, 13 Sep 2017 21:11:24 -0700 Subject: 3995 --- html/020run.cc.html | 8 +- html/071deep_copy.cc.html | 525 +++++++++++++++++++++++++++++ html/071recipe.cc.html | 464 -------------------------- html/072recipe.cc.html | 464 ++++++++++++++++++++++++++ html/072scheduler.cc.html | 775 ------------------------------------------- html/073scheduler.cc.html | 761 ++++++++++++++++++++++++++++++++++++++++++ html/073wait.cc.html | 670 ------------------------------------- html/074deep_copy.cc.html | 458 ------------------------- html/074wait.cc.html | 670 +++++++++++++++++++++++++++++++++++++ html/076continuation.cc.html | 12 +- 10 files changed, 2430 insertions(+), 2377 deletions(-) create mode 100644 html/071deep_copy.cc.html delete mode 100644 html/071recipe.cc.html create mode 100644 html/072recipe.cc.html delete mode 100644 html/072scheduler.cc.html create mode 100644 html/073scheduler.cc.html delete mode 100644 html/073wait.cc.html delete mode 100644 html/074deep_copy.cc.html create mode 100644 html/074wait.cc.html (limited to 'html') diff --git a/html/020run.cc.html b/html/020run.cc.html index d55ea087..418d1eae 100644 --- a/html/020run.cc.html +++ b/html/020run.cc.html @@ -127,7 +127,7 @@ if ('onhashchange' in window) { 60 } 61 62 void run_current_routine() { - 63 while (should_continue_running(Current_routine)) { // beware: may modify Current_routine + 63 while (should_continue_running(Current_routine)) { // beware: may modify Current_routine 64 ¦ // Running One Instruction 65 ¦ if (current_instruction().is_label) { ++current_step_index(); continue; } 66 ¦ trace(Initial_callstack_depth + Trace_stream->callstack_depth, "run") << to_string(current_instruction()) << end(); @@ -183,7 +183,7 @@ if ('onhashchange' in window) { 116 117 :(code) 118 //: hook replaced in a later layer -119 bool should_continue_running(const routine* current_routine) { +119 bool should_continue_running(const routine* current_routine) { 120 assert(current_routine == Current_routine); // argument passed in just to make caller readable above 121 return !Current_routine->completed(); 122 } @@ -282,10 +282,10 @@ if ('onhashchange' in window) { 215 } 216 trace(2, "run") << "=== Starting to run" << end(); 217 assert(Num_calls_to_transform_all == 1); -218 run_main(argc, argv); +218 run_main(argc, argv); 219 } 220 :(code) -221 void run_main(int argc, char* argv[]) { +221 void run_main(int argc, char* argv[]) { 222 recipe_ordinal r = get(Recipe_ordinal, "main"); 223 if (r) run(r); 224 } diff --git a/html/071deep_copy.cc.html b/html/071deep_copy.cc.html new file mode 100644 index 00000000..56fb82fe --- /dev/null +++ b/html/071deep_copy.cc.html @@ -0,0 +1,525 @@ + + + + +Mu - 071deep_copy.cc + + + + + + + + + + +
+  1 // To recursively copy containers and any addresses they contain, use
+  2 // 'deep-copy'.
+  3 //
+  4 // Invariant: After a deep-copy its ingredient and result will point to no
+  5 // common addresses.
+  6 // Implications: Refcounts of all data pointed to by the original ingredient
+  7 // will remain unchanged. Refcounts of all data pointed to by the (newly
+  8 // created) result will be 1, in the absence of cycles.
+  9 //
+ 10 // We do handle cycles in the ingredient, however. All cycles are translated
+ 11 // to new cycles in the product.
+ 12 
+ 13 :(scenario deep_copy_number)
+ 14 def main [
+ 15   local-scope
+ 16   x:num <- copy 34
+ 17   y:num <- deep-copy x
+ 18   10:bool/raw <- equal x, y
+ 19 ]
+ 20 # non-address primitives are identical
+ 21 +mem: storing 1 in location 10
+ 22 
+ 23 :(scenario deep_copy_container_without_address)
+ 24 container foo [
+ 25   x:num
+ 26   y:num
+ 27 ]
+ 28 def main [
+ 29   local-scope
+ 30   a:foo <- merge 34, 35
+ 31   b:foo <- deep-copy a
+ 32   10:bool/raw <- equal a, b
+ 33 ]
+ 34 # containers are identical as long as they don't contain addresses
+ 35 +mem: storing 1 in location 10
+ 36 
+ 37 :(scenario deep_copy_address)
+ 38 % Memory_allocated_until = 200;
+ 39 def main [
+ 40   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 41   # that the result is deterministic
+ 42   1:&:num <- copy 100/unsafe  # pretend allocation
+ 43   *1:&:num <- copy 34
+ 44   2:&:num <- deep-copy 1:&:num
+ 45   10:bool <- equal 1:&:num, 2:&:num
+ 46   11:bool <- equal *1:&:num, *2:&:num
+ 47   2:&:num <- copy 0
+ 48 ]
+ 49 # the result of deep-copy is a new address
+ 50 +mem: storing 0 in location 10
+ 51 # however, the contents are identical
+ 52 +mem: storing 1 in location 11
+ 53 # the result of deep-copy gets a refcount of 1
+ 54 # (its address 202 = 200 base + 2 for temporary space inside deep-copy)
+ 55 +run: {2: ("address" "number")} <- copy {0: "literal"}
+ 56 +mem: decrementing refcount of 202: 1 -> 0
+ 57 +abandon: saving 202 in free-list of size 2
+ 58 
+ 59 :(scenario deep_copy_address_to_container)
+ 60 % Memory_allocated_until = 200;
+ 61 def main [
+ 62   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 63   # that the result is deterministic
+ 64   1:&:point <- copy 100/unsafe  # pretend allocation
+ 65   *1:&:point <- merge 34, 35
+ 66   2:&:point <- deep-copy 1:&:point
+ 67   10:bool <- equal 1:&:point, 2:&:point
+ 68   11:bool <- equal *1:&:point, *2:&:point
+ 69 ]
+ 70 # the result of deep-copy is a new address
+ 71 +mem: storing 0 in location 10
+ 72 # however, the contents are identical
+ 73 +mem: storing 1 in location 11
+ 74 
+ 75 :(scenario deep_copy_address_to_address)
+ 76 % Memory_allocated_until = 200;
+ 77 def main [
+ 78   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 79   # that the result is deterministic
+ 80   1:&:&:num <- copy 100/unsafe  # pretend allocation
+ 81   *1:&:&:num <- copy 150/unsafe
+ 82   **1:&:&:num <- copy 34
+ 83   2:&:&:num <- deep-copy 1:&:&:num
+ 84   10:bool <- equal 1:&:&:num, 2:&:&:num
+ 85   11:bool <- equal *1:&:&:num, *2:&:&:num
+ 86   12:bool <- equal **1:&:&:num, **2:&:&:num
+ 87 ]
+ 88 # the result of deep-copy is a new address
+ 89 +mem: storing 0 in location 10
+ 90 # any addresses in it or pointed to it are also new
+ 91 +mem: storing 0 in location 11
+ 92 # however, the non-address contents are identical
+ 93 +mem: storing 1 in location 12
+ 94 
+ 95 :(scenario deep_copy_array)
+ 96 % Memory_allocated_until = 200;
+ 97 def main [
+ 98   # avoid all memory allocations except the implicit ones inside deep-copy, so
+ 99   # that the result is deterministic
+100   100:num <- copy 1  # pretend refcount
+101   101:num <- copy 3  # pretend array length
+102   1:&:@:num <- copy 100/unsafe  # pretend allocation
+103   put-index *1:&:@:num, 0, 34
+104   put-index *1:&:@:num, 1, 35
+105   put-index *1:&:@:num, 2, 36
+106   stash [old:], *1:&:@:num
+107   2:&:@:num <- deep-copy 1:&:@:num
+108   stash 2:&:@:num
+109   stash [new:], *2:&:@:num
+110   10:bool <- equal 1:&:@:num, 2:&:@:num
+111   11:bool <- equal *1:&:@:num, *2:&:@:num
+112 ]
+113 +app: old: 3 34 35 36
+114 +app: new: 3 34 35 36
+115 # the result of deep-copy is a new address
+116 +mem: storing 0 in location 10
+117 # however, the contents are identical
+118 +mem: storing 1 in location 11
+119 
+120 :(scenario deep_copy_container_with_address)
+121 container foo [
+122   x:num
+123   y:&:num
+124 ]
+125 def main [
+126   local-scope
+127   y0:&:num <- new number:type
+128   *y0 <- copy 35
+129   a:foo <- merge 34, y0
+130   b:foo <- deep-copy a
+131   10:bool/raw <- equal a, b
+132   y1:&:num <- get b, y:offset
+133   11:bool/raw <- equal y0, y1
+134   12:num/raw <- copy *y1
+135 ]
+136 # containers containing addresses are not identical to their deep copies
+137 +mem: storing 0 in location 10
+138 # the addresses they contain are not identical either
+139 +mem: storing 0 in location 11
+140 +mem: storing 35 in location 12
+141 
+142 :(scenario deep_copy_exclusive_container_with_address)
+143 exclusive-container foo [
+144   x:num
+145   y:&:num
+146 ]
+147 def main [
+148   local-scope
+149   y0:&:num <- new number:type
+150   *y0 <- copy 34
+151   a:foo <- merge 1/y, y0
+152   b:foo <- deep-copy a
+153   10:bool/raw <- equal a, b
+154   y1:&:num, z:bool <- maybe-convert b, y:variant
+155   11:bool/raw <- equal y0, y1
+156   12:num/raw <- copy *y1
+157 ]
+158 # exclusive containers containing addresses are not identical to their deep copies
+159 +mem: storing 0 in location 10
+160 # the addresses they contain are not identical either
+161 +mem: storing 0 in location 11
+162 +mem: storing 34 in location 12
+163 
+164 :(scenario deep_copy_exclusive_container_with_container_with_address)
+165 exclusive-container foo [
+166   x:num
+167   y:bar  # inline
+168 ]
+169 container bar [
+170   x:&:num
+171 ]
+172 def main [
+173   local-scope
+174   y0:&:num <- new number:type
+175   *y0 <- copy 34
+176   a:bar <- merge y0
+177   b:foo <- merge 1/y, a
+178   c:foo <- deep-copy b
+179   10:bool/raw <- equal b, c
+180   d:bar, z:bool <- maybe-convert c, y:variant
+181   y1:&:num <- get d, x:offset
+182   11:bool/raw <- equal y0, y1
+183   12:num/raw <- copy *y1
+184 ]
+185 # exclusive containers containing addresses are not identical to their deep copies
+186 +mem: storing 0 in location 10
+187 # sub-containers containing addresses are not identical either
+188 +mem: storing 0 in location 11
+189 +mem: storing 34 in location 12
+190 
+191 :(before "End Primitive Recipe Declarations")
+192 DEEP_COPY,
+193 :(before "End Primitive Recipe Numbers")
+194 put(Recipe_ordinal, "deep-copy", DEEP_COPY);
+195 :(before "End Primitive Recipe Checks")
+196 case DEEP_COPY: {
+197   if (SIZE(inst.ingredients) != 1) {
+198   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
+199   ¦ break;
+200   }
+201   if (SIZE(inst.products) != 1) {
+202   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
+203   ¦ break;
+204   }
+205   if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) {
+206   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << to_original_string(inst) << "'\n" << end();
+207   ¦ break;
+208   }
+209   break;
+210 }
+211 :(before "End Primitive Recipe Implementations")
+212 case DEEP_COPY: {
+213   products.push_back(deep_copy(current_instruction().ingredients.at(0)));
+214   break;
+215 }
+216 
+217 :(code)
+218 vector<double> deep_copy(const reagent& in) {
+219   // allocate a tiny bit of temporary space for deep_copy()
+220   trace(9991, "run") << "deep-copy: allocating space for temporary" << end();
+221   reagent tmp("tmp:address:number");
+222   tmp.set_value(allocate(1));
+223   map<int, int> addresses_copied;
+224   vector<double> result = deep_copy(in, addresses_copied, tmp);
+225   // reclaim Mu memory allocated for tmp
+226   trace(9991, "run") << "deep-copy: reclaiming temporary" << end();
+227   abandon(tmp.value, payload_type(tmp.type), payload_size(tmp));
+228   // reclaim host memory allocated for tmp.type when tmp goes out of scope
+229   return result;
+230 }
+231 
+232 vector<double> deep_copy(reagent/*copy*/ in, map<int, int>& addresses_copied, const reagent& tmp) {
+233   canonize(in);
+234   if (is_mu_address(in)) {
+235   ¦ // hack: skip primitive containers that do their own locking; they're designed to be shared between routines
+236   ¦ type_tree* payload = in.type->right;
+237   ¦ if (payload->left->name == "channel" || payload->left->name == "resources")
+238   ¦ ¦ return read_memory(in);
+239   }
+240   vector<double> result;
+241   if (is_mu_address(in))
+242   ¦ result.push_back(deep_copy_address(in, addresses_copied, tmp));
+243   else
+244   ¦ deep_copy(in, addresses_copied, tmp, result);
+245   return result;
+246 }
+247 
+248 // deep-copy an address and return a new address
+249 int deep_copy_address(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp) {
+250   if (canonized_in.value == 0) return 0;
+251   int in_address = payload_address(canonized_in);
+252   trace(9991, "run") << "deep-copy: copying address " << in_address << end();
+253   if (contains_key(addresses_copied, in_address)) {
+254   ¦ int out = get(addresses_copied, in_address);
+255   ¦ trace(9991, "run") << "deep-copy: copy already exists: " << out << end();
+256   ¦ return out;
+257   }
+258   int out = allocate(payload_size(canonized_in));
+259   trace(9991, "run") << "deep-copy: new address is " << out << end();
+260   put(addresses_copied, in_address, out);
+261   reagent/*copy*/ payload = canonized_in;
+262   payload.properties.push_back(pair<string, string_tree*>("lookup", NULL));
+263   trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end();
+264   vector<double> data = deep_copy(payload, addresses_copied, tmp);
+265   trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end();
+266   // HACK: write_memory interface isn't ideal for this situation; we need
+267   // a temporary location to help copy the payload.
+268   trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end();
+269   put(Memory, tmp.value, out);
+270   payload.set_value(tmp.value);  // now modified for output
+271   vector<double> old_data = read_memory(payload);
+272   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();
+273   write_memory(payload, data);
+274   trace(9991, "run") << "deep-copy: output is " << to_string(data) << end();
+275   return out;
+276 }
+277 
+278 // deep-copy a non-address and return a vector of locations
+279 void deep_copy(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp, vector<double>& out) {
+280   assert(!is_mu_address(canonized_in));
+281   vector<double> data = read_memory(canonized_in);
+282   out.insert(out.end(), data.begin(), data.end());
+283   if (!contains_key(Container_metadata, canonized_in.type)) return;
+284   trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end();
+285   const container_metadata& metadata = get(Container_metadata, canonized_in.type);
+286   for (map<set<tag_condition_info>, set<address_element_info> >::const_iterator p = metadata.address.begin();  p != metadata.address.end();  ++p) {
+287   ¦ if (!all_match(data, p->first)) continue;
+288   ¦ for (set<address_element_info>::const_iterator info = p->second.begin();  info != p->second.end();  ++info) {
+289   ¦ ¦ // hack: skip primitive containers that do their own locking; they're designed to be shared between routines
+290   ¦ ¦ if (!info->payload_type->atom && info->payload_type->left->name == "channel")
+291   ¦ ¦ ¦ continue;
+292   ¦ ¦ if (info->payload_type->atom && info->payload_type->name == "resources")
+293   ¦ ¦ ¦ continue;
+294   ¦ ¦ // construct a fake reagent that reads directly from the appropriate
+295   ¦ ¦ // field of the container
+296   ¦ ¦ reagent curr;
+297   ¦ ¦ if (info->payload_type->atom)
+298   ¦ ¦ ¦ curr.type = new type_tree(new type_tree("address"), new type_tree(new type_tree(info->payload_type->name), NULL));
+299   ¦ ¦ else
+300   ¦ ¦ ¦ curr.type = new type_tree(new type_tree("address"), new type_tree(*info->payload_type));
+301   ¦ ¦ curr.set_value(canonized_in.value + info->offset);
+302   ¦ ¦ curr.properties.push_back(pair<string, string_tree*>("raw", NULL));
+303   ¦ ¦ trace(9991, "run") << "deep-copy: copying address " << curr.value << end();
+304   ¦ ¦ out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp);
+305   ¦ }
+306   }
+307 }
+308 
+309 int payload_address(reagent/*copy*/ x) {
+310   x.properties.push_back(pair<string, string_tree*>("lookup", NULL));
+311   canonize(x);
+312   return x.value;
+313 }
+314 
+315 :(scenario deep_copy_stress_test_1)
+316 container foo1 [
+317   p:&:num
+318 ]
+319 container foo2 [
+320   p:&:foo1
+321 ]
+322 exclusive-container foo3 [
+323   p:&:foo1
+324   q:&:foo2
+325 ]
+326 def main [
+327   local-scope
+328   x:&:num <- new number:type
+329   *x <- copy 34
+330   a:&:foo1 <- new foo1:type
+331   *a <- merge x
+332   b:&:foo2 <- new foo2:type
+333   *b <- merge a
+334   c:foo3 <- merge 1/q, b
+335   d:foo3 <- deep-copy c
+336   e:&:foo2, z:bool <- maybe-convert d, q:variant
+337   f:&:foo1 <- get *e, p:offset
+338   g:&:num <- get *f, p:offset
+339   1:num/raw <- copy *g
+340 ]
+341 +mem: storing 34 in location 1
+342 
+343 :(scenario deep_copy_stress_test_2)
+344 container foo1 [
+345   p:&:num
+346 ]
+347 container foo2 [
+348   p:&:foo1
+349 ]
+350 exclusive-container foo3 [
+351   p:&:foo1
+352   q:&:foo2
+353 ]
+354 container foo4 [
+355   p:num
+356   q:&:foo3
+357 ]
+358 def main [
+359   local-scope
+360   x:&:num <- new number:type
+361   *x <- copy 34
+362   a:&:foo1 <- new foo1:type
+363   *a <- merge x
+364   b:&:foo2 <- new foo2:type
+365   *b <- merge a
+366   c:&:foo3 <- new foo3:type
+367   *c <- merge 1/q, b
+368   d:foo4 <- merge 35, c
+369   e:foo4 <- deep-copy d
+370   f:&:foo3 <- get e, q:offset
+371   g:&:foo2, z:bool <- maybe-convert *f, q:variant
+372   h:&:foo1 <- get *g, p:offset
+373   y:&:num <- get *h, p:offset
+374   1:num/raw <- copy *y
+375 ]
+376 +mem: storing 34 in location 1
+377 
+378 :(scenario deep_copy_cycles)
+379 container foo [
+380   p:num
+381   q:&:foo
+382 ]
+383 def main [
+384   local-scope
+385   x:&:foo <- new foo:type
+386   *x <- put *x, p:offset, 34
+387   *x <- put *x, q:offset, x  # create a cycle
+388   y:&:foo <- deep-copy x
+389   1:num/raw <- get *y, p:offset
+390   y2:&:foo <- get *y, q:offset
+391   stash y [vs] y2
+392   2:bool/raw <- equal y, y2  # is it still a cycle?
+393   3:bool/raw <- equal x, y  # is it the same cycle?
+394 ]
+395 +mem: storing 34 in location 1
+396 # deep copy also contains a cycle
+397 +mem: storing 1 in location 2
+398 # but it's a completely different (disjoint) cycle
+399 +mem: storing 0 in location 3
+400 
+401 :(scenario deep_copy_skips_channel)
+402 # ugly! dummy 'channel' type if we happen to be building without that layer
+403 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
+404 def main [
+405   local-scope
+406   x:&:channel:num <- new {(channel num): type}
+407   y:&:channel:num <- deep-copy x
+408   10:bool/raw <- equal x, y
+409 ]
+410 # channels are never deep-copied
+411 +mem: storing 1 in location 10
+412 
+413 :(scenario deep_copy_skips_nested_channel)
+414 # ugly! dummy 'channel' type if we happen to be building without that layer
+415 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
+416 container foo [
+417   c:&:channel:num
+418 ]
+419 def main [
+420   local-scope
+421   x:&:foo <- new foo:type
+422   y:&:foo <- deep-copy x
+423   xc:&:channel:num <- get *x, c:offset
+424   yc:&:channel:num <- get *y, c:offset
+425   10:bool/raw <- equal xc, yc
+426 ]
+427 # channels are never deep-copied
+428 +mem: storing 1 in location 10
+429 
+430 :(scenario deep_copy_skips_resources)
+431 # ugly! dummy 'resources' type if we happen to be building without that layer
+432 % if (!contains_key(Type_ordinal, "resources")) get_or_insert(Type, put(Type_ordinal, "resources", Next_type_ordinal++)).name = "resources";
+433 def main [
+434   local-scope
+435   x:&:resources <- new resources:type
+436   y:&:resources <- deep-copy x
+437   10:bool/raw <- equal x, y
+438 ]
+439 # resources are never deep-copied
+440 +mem: storing 1 in location 10
+441 
+442 :(scenario deep_copy_skips_nested_resources)
+443 # ugly! dummy 'resources' type if we happen to be building without that layer
+444 % if (!contains_key(Type_ordinal, "resources")) get_or_insert(Type, put(Type_ordinal, "resources", Next_type_ordinal++)).name = "resources";
+445 container foo [
+446   c:&:resources
+447 ]
+448 def main [
+449   local-scope
+450   x:&:foo <- new foo:type
+451   y:&:foo <- deep-copy x
+452   xc:&:resources <- get *x, c:offset
+453   yc:&:resources <- get *y, c:offset
+454   10:bool/raw <- equal xc, yc
+455 ]
+456 # resources are never deep-copied
+457 +mem: storing 1 in location 10
+
+ + + diff --git a/html/071recipe.cc.html b/html/071recipe.cc.html deleted file mode 100644 index fd82590d..00000000 --- a/html/071recipe.cc.html +++ /dev/null @@ -1,464 +0,0 @@ - - - - -Mu - 071recipe.cc - - - - - - - - - - -
-  1 //: So far we've been calling a fixed recipe in each instruction, but we'd
-  2 //: also like to make the recipe a variable, pass recipes to "higher-order"
-  3 //: recipes, return recipes from recipes and so on.
-  4 //:
-  5 //: todo: support storing shape-shifting recipes into recipe variables and calling them
-  6 
-  7 :(scenario call_literal_recipe)
-  8 def main [
-  9   1:num <- call f, 34
- 10 ]
- 11 def f x:num -> y:num [
- 12   local-scope
- 13   load-ingredients
- 14   y <- copy x
- 15 ]
- 16 +mem: storing 34 in location 1
- 17 
- 18 :(scenario call_variable)
- 19 def main [
- 20   {1: (recipe number -> number)} <- copy f
- 21   2:num <- call {1: (recipe number -> number)}, 34
- 22 ]
- 23 def f x:num -> y:num [
- 24   local-scope
- 25   load-ingredients
- 26   y <- copy x
- 27 ]
- 28 +mem: storing 34 in location 2
- 29 
- 30 :(before "End Mu Types Initialization")
- 31 put(Type_ordinal, "recipe-literal", 0);
- 32 // 'recipe' variables can store recipe-literal
- 33 type_ordinal recipe = put(Type_ordinal, "recipe", Next_type_ordinal++);
- 34 get_or_insert(Type, recipe).name = "recipe";
- 35 
- 36 :(after "Begin transform_names Ingredient Special-cases(ingredient, inst, caller)")
- 37 if (is_recipe_literal(ingredient, caller)) {
- 38   initialize_recipe_literal(ingredient);
- 39   continue;
- 40 }
- 41 :(after "Begin transform_names Product Special-cases(product, inst, caller)")
- 42 if (is_recipe_literal(product, caller)) {
- 43   initialize_recipe_literal(product);
- 44   continue;
- 45 }
- 46 :(code)
- 47 bool is_recipe_literal(const reagent& x, const recipe& caller) {
- 48   if (x.type) return false;
- 49   if (!contains_key(Recipe_ordinal, x.name)) return false;
- 50   if (contains_reagent_with_type(caller, x.name)) {
- 51   ¦ raise << maybe(caller.name) << "you can't use '" << x.name << "' as a recipe literal when it's also a variable\n" << end();
- 52   ¦ return false;
- 53   }
- 54   return true;
- 55 }
- 56 void initialize_recipe_literal(reagent& x) {
- 57   x.type = new type_tree("recipe-literal");
- 58   x.set_value(get(Recipe_ordinal, x.name));
- 59 }
- 60 bool contains_reagent_with_type(const recipe& caller, const string& name) {
- 61   for (int i = 0;  i < SIZE(caller.steps);  ++i) {
- 62   ¦ const instruction& inst = caller.steps.at(i);
- 63   ¦ for (int i = 0;  i < SIZE(inst.ingredients);  ++i)
- 64   ¦ ¦ if (is_matching_non_recipe_literal(inst.ingredients.at(i), name)) return true;
- 65   ¦ for (int i = 0;  i < SIZE(inst.products);  ++i)
- 66   ¦ ¦ if (is_matching_non_recipe_literal(inst.products.at(i), name)) return true;
- 67   }
- 68   return false;
- 69 }
- 70 bool is_matching_non_recipe_literal(const reagent& x, const string& name) {
- 71   if (x.name != name) return false;
- 72   if (!x.type) return false;
- 73   if (!x.type->atom) return false;
- 74   return x.type->value != get(Type_ordinal, "recipe-literal");
- 75 }
- 76 
- 77 //: It's confusing to use variable names that are also recipe names. Always
- 78 //: assume variable types override recipe literals.
- 79 :(scenario error_on_recipe_literal_used_as_a_variable)
- 80 % Hide_errors = true;
- 81 def main [
- 82   local-scope
- 83   a:bool <- equal break 0
- 84   break:bool <- copy 0
- 85 ]
- 86 +error: main: you can't use 'break' as a recipe literal when it's also a variable
- 87 +error: main: missing type for 'break' in 'a:bool <- equal break, 0'
- 88 
- 89 :(before "End Primitive Recipe Declarations")
- 90 CALL,
- 91 :(before "End Primitive Recipe Numbers")
- 92 put(Recipe_ordinal, "call", CALL);
- 93 :(before "End Primitive Recipe Checks")
- 94 case CALL: {
- 95   if (inst.ingredients.empty()) {
- 96   ¦ raise << maybe(get(Recipe, r).name) << "'call' requires at least one ingredient (the recipe to call)\n" << end();
- 97   ¦ break;
- 98   }
- 99   if (!is_mu_recipe(inst.ingredients.at(0))) {
-100   ¦ raise << maybe(get(Recipe, r).name) << "first ingredient of 'call' should be a recipe, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
-101   ¦ break;
-102   }
-103   break;
-104 }
-105 :(before "End Primitive Recipe Implementations")
-106 case CALL: {
-107   // Begin Call
-108   if (Trace_stream) {
-109   ¦ ++Trace_stream->callstack_depth;
-110   ¦ trace("trace") << "indirect 'call': incrementing callstack depth to " << Trace_stream->callstack_depth << end();
-111   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
-112   }
-113   if (!ingredients.at(0).at(0)) {
-114   ¦ raise << maybe(current_recipe_name()) << "tried to call empty recipe in '" << to_string(current_instruction()) << "'" << end();
-115   ¦ break;
-116   }
-117   const call& caller_frame = current_call();
-118   instruction/*copy*/ call_instruction = to_instruction(caller_frame);
-119   call_instruction.operation = ingredients.at(0).at(0);
-120   call_instruction.ingredients.erase(call_instruction.ingredients.begin());
-121   Current_routine->calls.push_front(call(ingredients.at(0).at(0)));
-122   ingredients.erase(ingredients.begin());  // drop the callee
-123   finish_call_housekeeping(call_instruction, ingredients);
-124   Num_refcount_updates[caller_frame.running_recipe][caller_frame.running_step_index]
-125   ¦ ¦ += (Total_refcount_updates - initial_num_refcount_updates);
-126   initial_num_refcount_updates = Total_refcount_updates;
-127   // not done with caller
-128   write_products = false;
-129   fall_through_to_next_instruction = false;
-130   break;
-131 }
-132 
-133 //:: check types for 'call' instructions
-134 
-135 :(scenario call_check_literal_recipe)
-136 % Hide_errors = true;
-137 def main [
-138   1:num <- call f, 34
-139 ]
-140 def f x:point -> y:point [
-141   local-scope
-142   load-ingredients
-143   y <- copy x
-144 ]
-145 +error: main: ingredient 0 has the wrong type at '1:num <- call f, 34'
-146 +error: main: product 0 has the wrong type at '1:num <- call f, 34'
-147 
-148 :(scenario call_check_variable_recipe)
-149 % Hide_errors = true;
-150 def main [
-151   {1: (recipe point -> point)} <- copy f
-152   2:num <- call {1: (recipe point -> point)}, 34
-153 ]
-154 def f x:point -> y:point [
-155   local-scope
-156   load-ingredients
-157   y <- copy x
-158 ]
-159 +error: main: ingredient 0 has the wrong type at '2:num <- call {1: (recipe point -> point)}, 34'
-160 +error: main: product 0 has the wrong type at '2:num <- call {1: (recipe point -> point)}, 34'
-161 
-162 :(after "Transform.push_back(check_instruction)")
-163 Transform.push_back(check_indirect_calls_against_header);  // idempotent
-164 :(code)
-165 void check_indirect_calls_against_header(const recipe_ordinal r) {
-166   trace(9991, "transform") << "--- type-check 'call' instructions inside recipe " << get(Recipe, r).name << end();
-167   const recipe& caller = get(Recipe, r);
-168   for (int i = 0;  i < SIZE(caller.steps);  ++i) {
-169   ¦ const instruction& inst = caller.steps.at(i);
-170   ¦ if (!is_indirect_call(inst.operation)) continue;
-171   ¦ if (inst.ingredients.empty()) continue;  // error raised above
-172   ¦ const reagent& callee = inst.ingredients.at(0);
-173   ¦ if (!is_mu_recipe(callee)) continue;  // error raised above
-174   ¦ const recipe callee_header = is_literal(callee) ? get(Recipe, callee.value) : from_reagent(inst.ingredients.at(0));
-175   ¦ if (!callee_header.has_header) continue;
-176   ¦ if (is_indirect_call_with_ingredients(inst.operation)) {
-177   ¦ ¦ for (long int i = /*skip callee*/1;  i < min(SIZE(inst.ingredients), SIZE(callee_header.ingredients)+/*skip callee*/1);  ++i) {
-178   ¦ ¦ ¦ if (!types_coercible(callee_header.ingredients.at(i-/*skip callee*/1), inst.ingredients.at(i)))
-179   ¦ ¦ ¦ ¦ raise << maybe(caller.name) << "ingredient " << i-/*skip callee*/1 << " has the wrong type at '" << to_original_string(inst) << "'\n" << end();
-180   ¦ ¦ }
-181   ¦ }
-182   ¦ if (is_indirect_call_with_products(inst.operation)) {
-183   ¦ ¦ for (long int i = 0;  i < min(SIZE(inst.products), SIZE(callee_header.products));  ++i) {
-184   ¦ ¦ ¦ if (is_dummy(inst.products.at(i))) continue;
-185   ¦ ¦ ¦ if (!types_coercible(callee_header.products.at(i), inst.products.at(i)))
-186   ¦ ¦ ¦ ¦ raise << maybe(caller.name) << "product " << i << " has the wrong type at '" << to_original_string(inst) << "'\n" << end();
-187   ¦ ¦ }
-188   ¦ }
-189   }
-190 }
-191 
-192 bool is_indirect_call(const recipe_ordinal r) {
-193   return is_indirect_call_with_ingredients(r) || is_indirect_call_with_products(r);
-194 }
-195 
-196 bool is_indirect_call_with_ingredients(const recipe_ordinal r) {
-197   if (r == CALL) return true;
-198   // End is_indirect_call_with_ingredients Special-cases
-199   return false;
-200 }
-201 bool is_indirect_call_with_products(const recipe_ordinal r) {
-202   if (r == CALL) return true;
-203   // End is_indirect_call_with_products Special-cases
-204   return false;
-205 }
-206 
-207 recipe from_reagent(const reagent& r) {
-208   assert(r.type);
-209   recipe result_header;  // will contain only ingredients and products, nothing else
-210   result_header.has_header = true;
-211   // Begin Reagent->Recipe(r, recipe_header)
-212   if (r.type->atom) {
-213   ¦ assert(r.type->name == "recipe");
-214   ¦ return result_header;
-215   }
-216   const type_tree* root_type = r.type->atom ? r.type : r.type->left;
-217   assert(root_type->atom);
-218   assert(root_type->name == "recipe");
-219   const type_tree* curr = r.type->right;
-220   for (/*nada*/;  curr && !curr->atom;  curr = curr->right) {
-221   ¦ if (curr->left->atom && curr->left->name == "->") {
-222   ¦ ¦ curr = curr->right;  // skip delimiter
-223   ¦ ¦ goto read_products;
-224   ¦ }
-225   ¦ result_header.ingredients.push_back(next_recipe_reagent(curr->left));
-226   }
-227   if (curr) {
-228   ¦ assert(curr->atom);
-229   ¦ result_header.ingredients.push_back(next_recipe_reagent(curr));
-230   ¦ return result_header;  // no products
-231   }
-232   read_products:
-233   for (/*nada*/;  curr && !curr->atom;  curr = curr->right)
-234   ¦ result_header.products.push_back(next_recipe_reagent(curr->left));
-235   if (curr) {
-236   ¦ assert(curr->atom);
-237   ¦ result_header.products.push_back(next_recipe_reagent(curr));
-238   }
-239   return result_header;
-240 }
-241 
-242 :(before "End Unit Tests")
-243 void test_from_reagent_atomic() {
-244   reagent a("{f: recipe}");
-245   recipe r_header = from_reagent(a);
-246   CHECK(r_header.ingredients.empty());
-247   CHECK(r_header.products.empty());
-248 }
-249 void test_from_reagent_non_atomic() {
-250   reagent a("{f: (recipe number -> number)}");
-251   recipe r_header = from_reagent(a);
-252   CHECK_EQ(SIZE(r_header.ingredients), 1);
-253   CHECK_EQ(SIZE(r_header.products), 1);
-254 }
-255 void test_from_reagent_reads_ingredient_at_end() {
-256   reagent a("{f: (recipe number number)}");
-257   recipe r_header = from_reagent(a);
-258   CHECK_EQ(SIZE(r_header.ingredients), 2);
-259   CHECK(r_header.products.empty());
-260 }
-261 void test_from_reagent_reads_sole_ingredient_at_end() {
-262   reagent a("{f: (recipe number)}");
-263   recipe r_header = from_reagent(a);
-264   CHECK_EQ(SIZE(r_header.ingredients), 1);
-265   CHECK(r_header.products.empty());
-266 }
-267 
-268 :(code)
-269 reagent next_recipe_reagent(const type_tree* curr) {
-270   if (!curr->left) return reagent("recipe:"+curr->name);
-271   reagent result;
-272   result.name = "recipe";
-273   result.type = new type_tree(*curr);
-274   return result;
-275 }
-276 
-277 bool is_mu_recipe(const reagent& r) {
-278   if (!r.type) return false;
-279   if (r.type->atom) {
-280   ¦ // End is_mu_recipe Atom Cases(r)
-281   ¦ return r.type->name == "recipe-literal";
-282   }
-283   return r.type->left->atom && r.type->left->name == "recipe";
-284 }
-285 
-286 :(scenario copy_typecheck_recipe_variable)
-287 % Hide_errors = true;
-288 def main [
-289   3:num <- copy 34  # abc def
-290   {1: (recipe number -> number)} <- copy f  # store literal in a matching variable
-291   {2: (recipe boolean -> boolean)} <- copy {1: (recipe number -> number)}  # mismatch between recipe variables
-292 ]
-293 def f x:num -> y:num [
-294   local-scope
-295   load-ingredients
-296   y <- copy x
-297 ]
-298 +error: main: can't copy '{1: (recipe number -> number)}' to '{2: (recipe boolean -> boolean)}'; types don't match
-299 
-300 :(scenario copy_typecheck_recipe_variable_2)
-301 % Hide_errors = true;
-302 def main [
-303   {1: (recipe number -> number)} <- copy f  # mismatch with a recipe literal
-304 ]
-305 def f x:bool -> y:bool [
-306   local-scope
-307   load-ingredients
-308   y <- copy x
-309 ]
-310 +error: main: can't copy 'f' to '{1: (recipe number -> number)}'; types don't match
-311 
-312 :(before "End Matching Types For Literal(to)")
-313 if (is_mu_recipe(to)) {
-314   if (!contains_key(Recipe, from.value)) {
-315   ¦ raise << "trying to store recipe " << from.name << " into " << to_string(to) << " but there's no such recipe\n" << end();
-316   ¦ return false;
-317   }
-318   const recipe& rrhs = get(Recipe, from.value);
-319   const recipe& rlhs = from_reagent(to);
-320   for (long int i = 0;  i < min(SIZE(rlhs.ingredients), SIZE(rrhs.ingredients));  ++i) {
-321   ¦ if (!types_match(rlhs.ingredients.at(i), rrhs.ingredients.at(i)))
-322   ¦ ¦ return false;
-323   }
-324   for (long int i = 0;  i < min(SIZE(rlhs.products), SIZE(rrhs.products));  ++i) {
-325   ¦ if (!types_match(rlhs.products.at(i), rrhs.products.at(i)))
-326   ¦ ¦ return false;
-327   }
-328   return true;
-329 }
-330 
-331 :(scenario call_variable_compound_ingredient)
-332 def main [
-333   {1: (recipe (address number) -> number)} <- copy f
-334   2:&:num <- copy 0
-335   3:num <- call {1: (recipe (address number) -> number)}, 2:&:num
-336 ]
-337 def f x:&:num -> y:num [
-338   local-scope
-339   load-ingredients
-340   y <- copy x
-341 ]
-342 $error: 0
-343 
-344 //: make sure we don't accidentally break on a function literal
-345 :(scenario jump_forbidden_on_recipe_literals)
-346 % Hide_errors = true;
-347 def foo [
-348   local-scope
-349 ]
-350 def main [
-351   local-scope
-352   {
-353   ¦ break-if foo
-354   }
-355 ]
-356 # error should be as if foo is not a recipe
-357 +error: main: missing type for 'foo' in 'break-if foo'
-358 
-359 :(before "End JUMP_IF Checks")
-360 check_for_recipe_literals(inst, get(Recipe, r));
-361 :(before "End JUMP_UNLESS Checks")
-362 check_for_recipe_literals(inst, get(Recipe, r));
-363 :(code)
-364 void check_for_recipe_literals(const instruction& inst, const recipe& caller) {
-365   for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
-366   ¦ if (is_mu_recipe(inst.ingredients.at(i))) {
-367   ¦ ¦ raise << maybe(caller.name) << "missing type for '" << inst.ingredients.at(i).original_string << "' in '" << to_original_string(inst) << "'\n" << end();
-368   ¦ ¦ if (is_present_in_ingredients(caller, inst.ingredients.at(i).name))
-369   ¦ ¦ ¦ raise << "  did you forget 'load-ingredients'?\n" << end();
-370   ¦ }
-371   }
-372 }
-373 
-374 :(scenario load_ingredients_missing_error_3)
-375 % Hide_errors = true;
-376 def foo {f: (recipe num -> num)} [
-377   local-scope
-378   b:num <- call f, 1
-379 ]
-380 +error: foo: missing type for 'f' in 'b:num <- call f, 1'
-381 +error:   did you forget 'load-ingredients'?
-382 
-383 :(before "End Mu Types Initialization")
-384 put(Type_abbreviations, "function", new_type_tree("recipe"));
-385 
-386 :(scenario call_function)
-387 def main [
-388   {1: (function number -> number)} <- copy f
-389   2:num <- call {1: (function number -> number)}, 34
-390 ]
-391 def f x:num -> y:num [
-392   local-scope
-393   load-ingredients
-394   y <- copy x
-395 ]
-396 +mem: storing 34 in location 2
-
- - - diff --git a/html/072recipe.cc.html b/html/072recipe.cc.html new file mode 100644 index 00000000..9b03b055 --- /dev/null +++ b/html/072recipe.cc.html @@ -0,0 +1,464 @@ + + + + +Mu - 072recipe.cc + + + + + + + + + + +
+  1 //: So far we've been calling a fixed recipe in each instruction, but we'd
+  2 //: also like to make the recipe a variable, pass recipes to "higher-order"
+  3 //: recipes, return recipes from recipes and so on.
+  4 //:
+  5 //: todo: support storing shape-shifting recipes into recipe variables and calling them
+  6 
+  7 :(scenario call_literal_recipe)
+  8 def main [
+  9   1:num <- call f, 34
+ 10 ]
+ 11 def f x:num -> y:num [
+ 12   local-scope
+ 13   load-ingredients
+ 14   y <- copy x
+ 15 ]
+ 16 +mem: storing 34 in location 1
+ 17 
+ 18 :(scenario call_variable)
+ 19 def main [
+ 20   {1: (recipe number -> number)} <- copy f
+ 21   2:num <- call {1: (recipe number -> number)}, 34
+ 22 ]
+ 23 def f x:num -> y:num [
+ 24   local-scope
+ 25   load-ingredients
+ 26   y <- copy x
+ 27 ]
+ 28 +mem: storing 34 in location 2
+ 29 
+ 30 :(before "End Mu Types Initialization")
+ 31 put(Type_ordinal, "recipe-literal", 0);
+ 32 // 'recipe' variables can store recipe-literal
+ 33 type_ordinal recipe = put(Type_ordinal, "recipe", Next_type_ordinal++);
+ 34 get_or_insert(Type, recipe).name = "recipe";
+ 35 
+ 36 :(after "Begin transform_names Ingredient Special-cases(ingredient, inst, caller)")
+ 37 if (is_recipe_literal(ingredient, caller)) {
+ 38   initialize_recipe_literal(ingredient);
+ 39   continue;
+ 40 }
+ 41 :(after "Begin transform_names Product Special-cases(product, inst, caller)")
+ 42 if (is_recipe_literal(product, caller)) {
+ 43   initialize_recipe_literal(product);
+ 44   continue;
+ 45 }
+ 46 :(code)
+ 47 bool is_recipe_literal(const reagent& x, const recipe& caller) {
+ 48   if (x.type) return false;
+ 49   if (!contains_key(Recipe_ordinal, x.name)) return false;
+ 50   if (contains_reagent_with_type(caller, x.name)) {
+ 51   ¦ raise << maybe(caller.name) << "you can't use '" << x.name << "' as a recipe literal when it's also a variable\n" << end();
+ 52   ¦ return false;
+ 53   }
+ 54   return true;
+ 55 }
+ 56 void initialize_recipe_literal(reagent& x) {
+ 57   x.type = new type_tree("recipe-literal");
+ 58   x.set_value(get(Recipe_ordinal, x.name));
+ 59 }
+ 60 bool contains_reagent_with_type(const recipe& caller, const string& name) {
+ 61   for (int i = 0;  i < SIZE(caller.steps);  ++i) {
+ 62   ¦ const instruction& inst = caller.steps.at(i);
+ 63   ¦ for (int i = 0;  i < SIZE(inst.ingredients);  ++i)
+ 64   ¦ ¦ if (is_matching_non_recipe_literal(inst.ingredients.at(i), name)) return true;
+ 65   ¦ for (int i = 0;  i < SIZE(inst.products);  ++i)
+ 66   ¦ ¦ if (is_matching_non_recipe_literal(inst.products.at(i), name)) return true;
+ 67   }
+ 68   return false;
+ 69 }
+ 70 bool is_matching_non_recipe_literal(const reagent& x, const string& name) {
+ 71   if (x.name != name) return false;
+ 72   if (!x.type) return false;
+ 73   if (!x.type->atom) return false;
+ 74   return x.type->value != get(Type_ordinal, "recipe-literal");
+ 75 }
+ 76 
+ 77 //: It's confusing to use variable names that are also recipe names. Always
+ 78 //: assume variable types override recipe literals.
+ 79 :(scenario error_on_recipe_literal_used_as_a_variable)
+ 80 % Hide_errors = true;
+ 81 def main [
+ 82   local-scope
+ 83   a:bool <- equal break 0
+ 84   break:bool <- copy 0
+ 85 ]
+ 86 +error: main: you can't use 'break' as a recipe literal when it's also a variable
+ 87 +error: main: missing type for 'break' in 'a:bool <- equal break, 0'
+ 88 
+ 89 :(before "End Primitive Recipe Declarations")
+ 90 CALL,
+ 91 :(before "End Primitive Recipe Numbers")
+ 92 put(Recipe_ordinal, "call", CALL);
+ 93 :(before "End Primitive Recipe Checks")
+ 94 case CALL: {
+ 95   if (inst.ingredients.empty()) {
+ 96   ¦ raise << maybe(get(Recipe, r).name) << "'call' requires at least one ingredient (the recipe to call)\n" << end();
+ 97   ¦ break;
+ 98   }
+ 99   if (!is_mu_recipe(inst.ingredients.at(0))) {
+100   ¦ raise << maybe(get(Recipe, r).name) << "first ingredient of 'call' should be a recipe, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
+101   ¦ break;
+102   }
+103   break;
+104 }
+105 :(before "End Primitive Recipe Implementations")
+106 case CALL: {
+107   // Begin Call
+108   if (Trace_stream) {
+109   ¦ ++Trace_stream->callstack_depth;
+110   ¦ trace("trace") << "indirect 'call': incrementing callstack depth to " << Trace_stream->callstack_depth << end();
+111   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
+112   }
+113   if (!ingredients.at(0).at(0)) {
+114   ¦ raise << maybe(current_recipe_name()) << "tried to call empty recipe in '" << to_string(current_instruction()) << "'" << end();
+115   ¦ break;
+116   }
+117   const call& caller_frame = current_call();
+118   instruction/*copy*/ call_instruction = to_instruction(caller_frame);
+119   call_instruction.operation = ingredients.at(0).at(0);
+120   call_instruction.ingredients.erase(call_instruction.ingredients.begin());
+121   Current_routine->calls.push_front(call(ingredients.at(0).at(0)));
+122   ingredients.erase(ingredients.begin());  // drop the callee
+123   finish_call_housekeeping(call_instruction, ingredients);
+124   Num_refcount_updates[caller_frame.running_recipe][caller_frame.running_step_index]
+125   ¦ ¦ += (Total_refcount_updates - initial_num_refcount_updates);
+126   initial_num_refcount_updates = Total_refcount_updates;
+127   // not done with caller
+128   write_products = false;
+129   fall_through_to_next_instruction = false;
+130   break;
+131 }
+132 
+133 //:: check types for 'call' instructions
+134 
+135 :(scenario call_check_literal_recipe)
+136 % Hide_errors = true;
+137 def main [
+138   1:num <- call f, 34
+139 ]
+140 def f x:point -> y:point [
+141   local-scope
+142   load-ingredients
+143   y <- copy x
+144 ]
+145 +error: main: ingredient 0 has the wrong type at '1:num <- call f, 34'
+146 +error: main: product 0 has the wrong type at '1:num <- call f, 34'
+147 
+148 :(scenario call_check_variable_recipe)
+149 % Hide_errors = true;
+150 def main [
+151   {1: (recipe point -> point)} <- copy f
+152   2:num <- call {1: (recipe point -> point)}, 34
+153 ]
+154 def f x:point -> y:point [
+155   local-scope
+156   load-ingredients
+157   y <- copy x
+158 ]
+159 +error: main: ingredient 0 has the wrong type at '2:num <- call {1: (recipe point -> point)}, 34'
+160 +error: main: product 0 has the wrong type at '2:num <- call {1: (recipe point -> point)}, 34'
+161 
+162 :(after "Transform.push_back(check_instruction)")
+163 Transform.push_back(check_indirect_calls_against_header);  // idempotent
+164 :(code)
+165 void check_indirect_calls_against_header(const recipe_ordinal r) {
+166   trace(9991, "transform") << "--- type-check 'call' instructions inside recipe " << get(Recipe, r).name << end();
+167   const recipe& caller = get(Recipe, r);
+168   for (int i = 0;  i < SIZE(caller.steps);  ++i) {
+169   ¦ const instruction& inst = caller.steps.at(i);
+170   ¦ if (!is_indirect_call(inst.operation)) continue;
+171   ¦ if (inst.ingredients.empty()) continue;  // error raised above
+172   ¦ const reagent& callee = inst.ingredients.at(0);
+173   ¦ if (!is_mu_recipe(callee)) continue;  // error raised above
+174   ¦ const recipe callee_header = is_literal(callee) ? get(Recipe, callee.value) : from_reagent(inst.ingredients.at(0));
+175   ¦ if (!callee_header.has_header) continue;
+176   ¦ if (is_indirect_call_with_ingredients(inst.operation)) {
+177   ¦ ¦ for (long int i = /*skip callee*/1;  i < min(SIZE(inst.ingredients), SIZE(callee_header.ingredients)+/*skip callee*/1);  ++i) {
+178   ¦ ¦ ¦ if (!types_coercible(callee_header.ingredients.at(i-/*skip callee*/1), inst.ingredients.at(i)))
+179   ¦ ¦ ¦ ¦ raise << maybe(caller.name) << "ingredient " << i-/*skip callee*/1 << " has the wrong type at '" << to_original_string(inst) << "'\n" << end();
+180   ¦ ¦ }
+181   ¦ }
+182   ¦ if (is_indirect_call_with_products(inst.operation)) {
+183   ¦ ¦ for (long int i = 0;  i < min(SIZE(inst.products), SIZE(callee_header.products));  ++i) {
+184   ¦ ¦ ¦ if (is_dummy(inst.products.at(i))) continue;
+185   ¦ ¦ ¦ if (!types_coercible(callee_header.products.at(i), inst.products.at(i)))
+186   ¦ ¦ ¦ ¦ raise << maybe(caller.name) << "product " << i << " has the wrong type at '" << to_original_string(inst) << "'\n" << end();
+187   ¦ ¦ }
+188   ¦ }
+189   }
+190 }
+191 
+192 bool is_indirect_call(const recipe_ordinal r) {
+193   return is_indirect_call_with_ingredients(r) || is_indirect_call_with_products(r);
+194 }
+195 
+196 bool is_indirect_call_with_ingredients(const recipe_ordinal r) {
+197   if (r == CALL) return true;
+198   // End is_indirect_call_with_ingredients Special-cases
+199   return false;
+200 }
+201 bool is_indirect_call_with_products(const recipe_ordinal r) {
+202   if (r == CALL) return true;
+203   // End is_indirect_call_with_products Special-cases
+204   return false;
+205 }
+206 
+207 recipe from_reagent(const reagent& r) {
+208   assert(r.type);
+209   recipe result_header;  // will contain only ingredients and products, nothing else
+210   result_header.has_header = true;
+211   // Begin Reagent->Recipe(r, recipe_header)
+212   if (r.type->atom) {
+213   ¦ assert(r.type->name == "recipe");
+214   ¦ return result_header;
+215   }
+216   const type_tree* root_type = r.type->atom ? r.type : r.type->left;
+217   assert(root_type->atom);
+218   assert(root_type->name == "recipe");
+219   const type_tree* curr = r.type->right;
+220   for (/*nada*/;  curr && !curr->atom;  curr = curr->right) {
+221   ¦ if (curr->left->atom && curr->left->name == "->") {
+222   ¦ ¦ curr = curr->right;  // skip delimiter
+223   ¦ ¦ goto read_products;
+224   ¦ }
+225   ¦ result_header.ingredients.push_back(next_recipe_reagent(curr->left));
+226   }
+227   if (curr) {
+228   ¦ assert(curr->atom);
+229   ¦ result_header.ingredients.push_back(next_recipe_reagent(curr));
+230   ¦ return result_header;  // no products
+231   }
+232   read_products:
+233   for (/*nada*/;  curr && !curr->atom;  curr = curr->right)
+234   ¦ result_header.products.push_back(next_recipe_reagent(curr->left));
+235   if (curr) {
+236   ¦ assert(curr->atom);
+237   ¦ result_header.products.push_back(next_recipe_reagent(curr));
+238   }
+239   return result_header;
+240 }
+241 
+242 :(before "End Unit Tests")
+243 void test_from_reagent_atomic() {
+244   reagent a("{f: recipe}");
+245   recipe r_header = from_reagent(a);
+246   CHECK(r_header.ingredients.empty());
+247   CHECK(r_header.products.empty());
+248 }
+249 void test_from_reagent_non_atomic() {
+250   reagent a("{f: (recipe number -> number)}");
+251   recipe r_header = from_reagent(a);
+252   CHECK_EQ(SIZE(r_header.ingredients), 1);
+253   CHECK_EQ(SIZE(r_header.products), 1);
+254 }
+255 void test_from_reagent_reads_ingredient_at_end() {
+256   reagent a("{f: (recipe number number)}");
+257   recipe r_header = from_reagent(a);
+258   CHECK_EQ(SIZE(r_header.ingredients), 2);
+259   CHECK(r_header.products.empty());
+260 }
+261 void test_from_reagent_reads_sole_ingredient_at_end() {
+262   reagent a("{f: (recipe number)}");
+263   recipe r_header = from_reagent(a);
+264   CHECK_EQ(SIZE(r_header.ingredients), 1);
+265   CHECK(r_header.products.empty());
+266 }
+267 
+268 :(code)
+269 reagent next_recipe_reagent(const type_tree* curr) {
+270   if (!curr->left) return reagent("recipe:"+curr->name);
+271   reagent result;
+272   result.name = "recipe";
+273   result.type = new type_tree(*curr);
+274   return result;
+275 }
+276 
+277 bool is_mu_recipe(const reagent& r) {
+278   if (!r.type) return false;
+279   if (r.type->atom) {
+280   ¦ // End is_mu_recipe Atom Cases(r)
+281   ¦ return r.type->name == "recipe-literal";
+282   }
+283   return r.type->left->atom && r.type->left->name == "recipe";
+284 }
+285 
+286 :(scenario copy_typecheck_recipe_variable)
+287 % Hide_errors = true;
+288 def main [
+289   3:num <- copy 34  # abc def
+290   {1: (recipe number -> number)} <- copy f  # store literal in a matching variable
+291   {2: (recipe boolean -> boolean)} <- copy {1: (recipe number -> number)}  # mismatch between recipe variables
+292 ]
+293 def f x:num -> y:num [
+294   local-scope
+295   load-ingredients
+296   y <- copy x
+297 ]
+298 +error: main: can't copy '{1: (recipe number -> number)}' to '{2: (recipe boolean -> boolean)}'; types don't match
+299 
+300 :(scenario copy_typecheck_recipe_variable_2)
+301 % Hide_errors = true;
+302 def main [
+303   {1: (recipe number -> number)} <- copy f  # mismatch with a recipe literal
+304 ]
+305 def f x:bool -> y:bool [
+306   local-scope
+307   load-ingredients
+308   y <- copy x
+309 ]
+310 +error: main: can't copy 'f' to '{1: (recipe number -> number)}'; types don't match
+311 
+312 :(before "End Matching Types For Literal(to)")
+313 if (is_mu_recipe(to)) {
+314   if (!contains_key(Recipe, from.value)) {
+315   ¦ raise << "trying to store recipe " << from.name << " into " << to_string(to) << " but there's no such recipe\n" << end();
+316   ¦ return false;
+317   }
+318   const recipe& rrhs = get(Recipe, from.value);
+319   const recipe& rlhs = from_reagent(to);
+320   for (long int i = 0;  i < min(SIZE(rlhs.ingredients), SIZE(rrhs.ingredients));  ++i) {
+321   ¦ if (!types_match(rlhs.ingredients.at(i), rrhs.ingredients.at(i)))
+322   ¦ ¦ return false;
+323   }
+324   for (long int i = 0;  i < min(SIZE(rlhs.products), SIZE(rrhs.products));  ++i) {
+325   ¦ if (!types_match(rlhs.products.at(i), rrhs.products.at(i)))
+326   ¦ ¦ return false;
+327   }
+328   return true;
+329 }
+330 
+331 :(scenario call_variable_compound_ingredient)
+332 def main [
+333   {1: (recipe (address number) -> number)} <- copy f
+334   2:&:num <- copy 0
+335   3:num <- call {1: (recipe (address number) -> number)}, 2:&:num
+336 ]
+337 def f x:&:num -> y:num [
+338   local-scope
+339   load-ingredients
+340   y <- copy x
+341 ]
+342 $error: 0
+343 
+344 //: make sure we don't accidentally break on a function literal
+345 :(scenario jump_forbidden_on_recipe_literals)
+346 % Hide_errors = true;
+347 def foo [
+348   local-scope
+349 ]
+350 def main [
+351   local-scope
+352   {
+353   ¦ break-if foo
+354   }
+355 ]
+356 # error should be as if foo is not a recipe
+357 +error: main: missing type for 'foo' in 'break-if foo'
+358 
+359 :(before "End JUMP_IF Checks")
+360 check_for_recipe_literals(inst, get(Recipe, r));
+361 :(before "End JUMP_UNLESS Checks")
+362 check_for_recipe_literals(inst, get(Recipe, r));
+363 :(code)
+364 void check_for_recipe_literals(const instruction& inst, const recipe& caller) {
+365   for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
+366   ¦ if (is_mu_recipe(inst.ingredients.at(i))) {
+367   ¦ ¦ raise << maybe(caller.name) << "missing type for '" << inst.ingredients.at(i).original_string << "' in '" << to_original_string(inst) << "'\n" << end();
+368   ¦ ¦ if (is_present_in_ingredients(caller, inst.ingredients.at(i).name))
+369   ¦ ¦ ¦ raise << "  did you forget 'load-ingredients'?\n" << end();
+370   ¦ }
+371   }
+372 }
+373 
+374 :(scenario load_ingredients_missing_error_3)
+375 % Hide_errors = true;
+376 def foo {f: (recipe num -> num)} [
+377   local-scope
+378   b:num <- call f, 1
+379 ]
+380 +error: foo: missing type for 'f' in 'b:num <- call f, 1'
+381 +error:   did you forget 'load-ingredients'?
+382 
+383 :(before "End Mu Types Initialization")
+384 put(Type_abbreviations, "function", new_type_tree("recipe"));
+385 
+386 :(scenario call_function)
+387 def main [
+388   {1: (function number -> number)} <- copy f
+389   2:num <- call {1: (function number -> number)}, 34
+390 ]
+391 def f x:num -> y:num [
+392   local-scope
+393   load-ingredients
+394   y <- copy x
+395 ]
+396 +mem: storing 34 in location 2
+
+ + + diff --git a/html/072scheduler.cc.html b/html/072scheduler.cc.html deleted file mode 100644 index 812f8691..00000000 --- a/html/072scheduler.cc.html +++ /dev/null @@ -1,775 +0,0 @@ - - - - -Mu - 072scheduler.cc - - - - - - - - - - -
-  1 //: Run a second routine concurrently using 'start-running', without any
-  2 //: guarantees on how the operations in each are interleaved with each other.
-  3 
-  4 :(scenario scheduler)
-  5 def f1 [
-  6   start-running f2
-  7   # wait for f2 to run
-  8   {
-  9   ¦ jump-unless 1:num, -1
- 10   }
- 11 ]
- 12 def f2 [
- 13   1:num <- copy 1
- 14 ]
- 15 +schedule: f1
- 16 +schedule: f2
- 17 
- 18 //: first, add a deadline to run(routine)
- 19 :(before "End Globals")
- 20 int Scheduling_interval = 500;
- 21 :(before "End routine Fields")
- 22 int instructions_run_this_scheduling_slice;
- 23 :(before "End routine Constructor")
- 24 instructions_run_this_scheduling_slice = 0;
- 25 :(after "Running One Instruction")
- 26  ++Current_routine->instructions_run_this_scheduling_slice;
- 27 :(replace{} "bool should_continue_running(const routine* current_routine)")
- 28 bool should_continue_running(const routine* current_routine) {
- 29   assert(current_routine == Current_routine);  // argument passed in just to make caller readable above
- 30   return Current_routine->state == RUNNING
- 31   ¦ ¦ && Current_routine->instructions_run_this_scheduling_slice < Scheduling_interval;
- 32 }
- 33 :(after "stop_running_current_routine:")
- 34 // Reset instructions_run_this_scheduling_slice
- 35 Current_routine->instructions_run_this_scheduling_slice = 0;
- 36 
- 37 //: now the rest of the scheduler is clean
- 38 
- 39 :(before "struct routine")
- 40 enum routine_state {
- 41   RUNNING,
- 42   COMPLETED,
- 43   // End routine States
- 44 };
- 45 :(before "End routine Fields")
- 46 enum routine_state state;
- 47 :(before "End routine Constructor")
- 48 state = RUNNING;
- 49 
- 50 :(before "End Globals")
- 51 vector<routine*> Routines;
- 52 int Current_routine_index = 0;
- 53 :(before "End Reset")
- 54 Scheduling_interval = 500;
- 55 for (int i = 0;  i < SIZE(Routines);  ++i)
- 56   delete Routines.at(i);
- 57 Routines.clear();
- 58 Current_routine = NULL;
- 59 :(replace{} "void run(const recipe_ordinal r)")
- 60 void run(const recipe_ordinal r) {
- 61   run(new routine(r));
- 62 }
- 63 
- 64 :(code)
- 65 void run(routine* rr) {
- 66   Routines.push_back(rr);
- 67   Current_routine_index = 0, Current_routine = Routines.at(0);
- 68   while (!all_routines_done()) {
- 69   ¦ skip_to_next_routine();
- 70   ¦ assert(Current_routine);
- 71   ¦ assert(Current_routine->state == RUNNING);
- 72   ¦ trace(9990, "schedule") << current_routine_label() << end();
- 73   ¦ run_current_routine();
- 74   ¦ // Scheduler State Transitions
- 75   ¦ if (Current_routine->completed())
- 76   ¦ ¦ Current_routine->state = COMPLETED;
- 77   ¦ // End Scheduler State Transitions
- 78 
- 79   ¦ // Scheduler Cleanup
- 80   ¦ // End Scheduler Cleanup
- 81   }
- 82   // End Run Routine
- 83 }
- 84 
- 85 bool all_routines_done() {
- 86   for (int i = 0;  i < SIZE(Routines);  ++i) {
- 87   ¦ if (Routines.at(i)->state == RUNNING)
- 88   ¦ ¦ return false;
- 89   }
- 90   return true;
- 91 }
- 92 
- 93 // skip Current_routine_index past non-RUNNING routines
- 94 void skip_to_next_routine() {
- 95   assert(!Routines.empty());
- 96   assert(Current_routine_index < SIZE(Routines));
- 97   for (int i = (Current_routine_index+1)%SIZE(Routines);  i != Current_routine_index;  i = (i+1)%SIZE(Routines)) {
- 98   ¦ if (Routines.at(i)->state == RUNNING) {
- 99   ¦ ¦ Current_routine_index = i;
-100   ¦ ¦ Current_routine = Routines.at(i);
-101   ¦ ¦ return;
-102   ¦ }
-103   }
-104 }
-105 
-106 string current_routine_label() {
-107   return routine_label(Current_routine);
-108 }
-109 
-110 string routine_label(routine* r) {
-111   ostringstream result;
-112   const call_stack& calls = r->calls;
-113   for (call_stack::const_iterator p = calls.begin();  p != calls.end();  ++p) {
-114   ¦ if (p != calls.begin()) result << '/';
-115   ¦ result << get(Recipe, p->running_recipe).name;
-116   }
-117   return result.str();
-118 }
-119 
-120 //: special case for the very first routine
-121 :(replace{} "void run_main(int argc, char* argv[])")
-122 void run_main(int argc, char* argv[]) {
-123   recipe_ordinal r = get(Recipe_ordinal, "main");
-124   assert(r);
-125   routine* main_routine = new routine(r);
-126   // pass in commandline args as ingredients to main
-127   // todo: test this
-128   Current_routine = main_routine;
-129   for (int i = 1;  i < argc;  ++i) {
-130   ¦ vector<double> arg;
-131   ¦ arg.push_back(new_mu_text(argv[i]));
-132   ¦ assert(get(Memory, arg.back()) == 0);
-133   ¦ put(Memory, arg.back(), 1);  // update refcount
-134   ¦ current_call().ingredient_atoms.push_back(arg);
-135   }
-136   run(main_routine);
-137 }
-138 
-139 //:: To schedule new routines to run, call 'start-running'.
-140 
-141 //: 'start-running' will return a unique id for the routine that was created.
-142 //: routine id is a number, but don't do any arithmetic on it
-143 :(before "End routine Fields")
-144 int id;
-145 :(before "End Globals")
-146 int Next_routine_id = 1;
-147 :(before "End Reset")
-148 Next_routine_id = 1;
-149 :(before "End routine Constructor")
-150 id = Next_routine_id;
-151 ++Next_routine_id;
-152 
-153 //: routines save the routine that spawned them
-154 :(before "End routine Fields")
-155 // todo: really should be routine_id, but that's less efficient.
-156 int parent_index;  // only < 0 if there's no parent_index
-157 :(before "End routine Constructor")
-158 parent_index = -1;
-159 
-160 :(before "End Primitive Recipe Declarations")
-161 START_RUNNING,
-162 :(before "End Primitive Recipe Numbers")
-163 put(Recipe_ordinal, "start-running", START_RUNNING);
-164 :(before "End Primitive Recipe Checks")
-165 case START_RUNNING: {
-166   if (inst.ingredients.empty()) {
-167   ¦ raise << maybe(get(Recipe, r).name) << "'start-running' requires at least one ingredient: the recipe to start running\n" << end();
-168   ¦ break;
-169   }
-170   if (!is_mu_recipe(inst.ingredients.at(0))) {
-171   ¦ 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();
-172   ¦ break;
-173   }
-174   break;
-175 }
-176 :(before "End Primitive Recipe Implementations")
-177 case START_RUNNING: {
-178   routine* new_routine = new routine(ingredients.at(0).at(0));
-179   new_routine->parent_index = Current_routine_index;
-180   // populate ingredients
-181   for (int i = 1;  i < SIZE(current_instruction().ingredients);  ++i) {
-182   ¦ new_routine->calls.front().ingredient_atoms.push_back(ingredients.at(i));
-183   ¦ reagent/*copy*/ ingredient = current_instruction().ingredients.at(i);
-184   ¦ canonize_type(ingredient);
-185   ¦ new_routine->calls.front().ingredients.push_back(ingredient);
-186   ¦ // End Populate start-running Ingredient
-187   }
-188   Routines.push_back(new_routine);
-189   products.resize(1);
-190   products.at(0).push_back(new_routine->id);
-191   break;
-192 }
-193 
-194 :(scenario scheduler_runs_single_routine)
-195 % Scheduling_interval = 1;
-196 def f1 [
-197   1:num <- copy 0
-198   2:num <- copy 0
-199 ]
-200 +schedule: f1
-201 +run: {1: "number"} <- copy {0: "literal"}
-202 +schedule: f1
-203 +run: {2: "number"} <- copy {0: "literal"}
-204 
-205 :(scenario scheduler_interleaves_routines)
-206 % Scheduling_interval = 1;
-207 def f1 [
-208   start-running f2
-209   1:num <- copy 0
-210   2:num <- copy 0
-211 ]
-212 def f2 [
-213   3:num <- copy 0
-214   4:num <- copy 0
-215 ]
-216 +schedule: f1
-217 +run: start-running {f2: "recipe-literal"}
-218 +schedule: f2
-219 +run: {3: "number"} <- copy {0: "literal"}
-220 +schedule: f1
-221 +run: {1: "number"} <- copy {0: "literal"}
-222 +schedule: f2
-223 +run: {4: "number"} <- copy {0: "literal"}
-224 +schedule: f1
-225 +run: {2: "number"} <- copy {0: "literal"}
-226 
-227 :(scenario start_running_takes_ingredients)
-228 def f1 [
-229   start-running f2, 3
-230   # wait for f2 to run
-231   {
-232   ¦ jump-unless 1:num, -1
-233   }
-234 ]
-235 def f2 [
-236   1:num <- next-ingredient
-237   2:num <- add 1:num, 1
-238 ]
-239 +mem: storing 4 in location 2
-240 
-241 //: type-checking for 'start-running'
-242 
-243 :(scenario start_running_checks_types)
-244 % Hide_errors = true;
-245 def f1 [
-246   start-running f2, 3
-247 ]
-248 def f2 n:&:num [
-249 ]
-250 +error: f1: ingredient 0 has the wrong type at 'start-running f2, 3'
-251 
-252 // 'start-running' only uses the ingredients of the callee, not its products
-253 :(before "End is_indirect_call_with_ingredients Special-cases")
-254 if (r == START_RUNNING) return true;
-255 
-256 //: more complex: refcounting management when starting up new routines
-257 
-258 :(scenario start_running_immediately_updates_refcounts_of_ingredients)
-259 % Scheduling_interval = 1;
-260 def main [
-261   local-scope
-262   create-new-routine
-263   # padding to make sure we run new-routine before returning
-264   dummy:num <- copy 0
-265   dummy:num <- copy 0
-266 ]
-267 def create-new-routine [
-268   local-scope
-269   n:&:num <- new number:type
-270   *n <- copy 34
-271   start-running new-routine, n
-272   # refcount of n decremented
-273 ]
-274 def new-routine n:&:num [
-275   local-scope
-276   load-ingredients
-277   1:num/raw <- copy *n
-278 ]
-279 # check that n wasn't reclaimed when create-new-routine returned
-280 +mem: storing 34 in location 1
-281 
-282 //: to support the previous scenario we'll increment refcounts for all call
-283 //: ingredients right at call time, and stop incrementing refcounts inside
-284 //: next-ingredient
-285 :(before "End Populate Call Ingredient")
-286 increment_any_refcounts(ingredient, ingredients.at(i));
-287 :(before "End Populate start-running Ingredient")
-288 increment_any_refcounts(ingredient, ingredients.at(i));
-289 :(after "should_update_refcounts() Special-cases When Writing Products Of Primitive Instructions")
-290 if (inst.operation == NEXT_INGREDIENT || inst.operation == NEXT_INGREDIENT_WITHOUT_TYPECHECKING) {
-291   if (space_index(inst.products.at(0)) > 0) return true;
-292   if (has_property(inst.products.at(0), "raw")) return true;
-293   return false;
-294 }
-295 
-296 // ensure this works with indirect calls using 'call' as well
-297 :(scenario start_running_immediately_updates_refcounts_of_ingredients_of_indirect_calls)
-298 % Scheduling_interval = 1;
-299 def main [
-300   local-scope
-301   n:&:num <- new number:type
-302   *n <- copy 34
-303   call f1, n
-304   1:num/raw <- copy *n
-305 ]
-306 def f1 n:&:num [
-307   local-scope
-308   load-ingredients
-309 ]
-310 # check that n wasn't reclaimed when f1 returned
-311 +mem: storing 34 in location 1
-312 
-313 :(scenario next_ingredient_never_leaks_refcounts)
-314 def create-space n:&:num -> default-space:space [
-315   default-space <- new location:type, 2
-316   load-ingredients
-317 ]
-318 def use-space [
-319   local-scope
-320   0:space/names:create-space <- next-ingredient
-321   n:&:num/space:1 <- next-ingredient  # should decrement refcount
-322   *n/space:1 <- copy 34
-323   n2:num <- add *n/space:1, 1
-324   return n2
-325 ]
-326 def main [
-327   local-scope
-328   n:&:num <- copy 12000/unsafe  # pretend allocation with a known address
-329   *n <- copy 23
-330   space:space <- create-space n
-331   n2:&:num <- copy 13000/unsafe
-332   n3:num <- use-space space, n2
-333 ]
-334 +run: {n: ("address" "number"), "space": "1"} <- next-ingredient
-335 +mem: decrementing refcount of 12000: 2 -> 1
-336 +run: {n: ("address" "number"), "space": "1", "lookup": ()} <- copy {34: "literal"}
-337 
-338 //: back to testing 'start-running'
-339 
-340 :(scenario start_running_returns_routine_id)
-341 def f1 [
-342   1:num <- start-running f2
-343 ]
-344 def f2 [
-345   12:num <- copy 44
-346 ]
-347 +mem: storing 2 in location 1
-348 
-349 //: this scenario will require some careful setup in escaped C++
-350 //: (straining our tangle capabilities to near-breaking point)
-351 :(scenario scheduler_skips_completed_routines)
-352 % recipe_ordinal f1 = load("recipe f1 [\n1:num <- copy 0\n]\n").front();
-353 % recipe_ordinal f2 = load("recipe f2 [\n2:num <- copy 0\n]\n").front();
-354 % Routines.push_back(new routine(f1));  // f1 meant to run
-355 % Routines.push_back(new routine(f2));
-356 % Routines.back()->state = COMPLETED;  // f2 not meant to run
-357 # must have at least one routine without escaping
-358 def f3 [
-359   3:num <- copy 0
-360 ]
-361 # by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order
-362 +schedule: f1
-363 +mem: storing 0 in location 1
-364 -schedule: f2
-365 -mem: storing 0 in location 2
-366 +schedule: f3
-367 +mem: storing 0 in location 3
-368 
-369 :(scenario scheduler_starts_at_middle_of_routines)
-370 % Routines.push_back(new routine(COPY));
-371 % Routines.back()->state = COMPLETED;
-372 def f1 [
-373   1:num <- copy 0
-374   2:num <- copy 0
-375 ]
-376 +schedule: f1
-377 -run: idle
-378 
-379 //:: Errors in a routine cause it to terminate.
-380 
-381 :(scenario scheduler_terminates_routines_after_errors)
-382 % Hide_errors = true;
-383 % Scheduling_interval = 2;
-384 def f1 [
-385   start-running f2
-386   1:num <- copy 0
-387   2:num <- copy 0
-388 ]
-389 def f2 [
-390   # divide by 0 twice
-391   3:num <- divide-with-remainder 4, 0
-392   4:num <- divide-with-remainder 4, 0
-393 ]
-394 # f2 should stop after first divide by 0
-395 +error: f2: divide by zero in '3:num <- divide-with-remainder 4, 0'
-396 -error: f2: divide by zero in '4:num <- divide-with-remainder 4, 0'
-397 
-398 :(after "operator<<(ostream& os, unused end)")
-399   if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) {
-400   ¦ Current_routine->state = COMPLETED;
-401   }
-402 
-403 //:: Routines are marked completed when their parent completes.
-404 
-405 :(scenario scheduler_kills_orphans)
-406 def main [
-407   start-running f1
-408   # f1 never actually runs because its parent completes without waiting for it
-409 ]
-410 def f1 [
-411   1:num <- copy 0
-412 ]
-413 -schedule: f1
-414 
-415 :(before "End Scheduler Cleanup")
-416 for (int i = 0;  i < SIZE(Routines);  ++i) {
-417   if (Routines.at(i)->state == COMPLETED) continue;
-418   if (Routines.at(i)->parent_index < 0) continue;  // root thread
-419   // structured concurrency: http://250bpm.com/blog:71
-420   if (has_completed_parent(i)) {
-421   ¦ Routines.at(i)->state = COMPLETED;
-422   }
-423 }
-424 
-425 :(code)
-426 bool has_completed_parent(int routine_index) {
-427   for (int j = routine_index;  j >= 0;  j = Routines.at(j)->parent_index) {
-428   ¦ if (Routines.at(j)->state == COMPLETED)
-429   ¦ ¦ return true;
-430   }
-431   return false;
-432 }
-433 
-434 //:: 'routine-state' can tell if a given routine id is running
-435 
-436 :(scenario routine_state_test)
-437 % Scheduling_interval = 2;
-438 def f1 [
-439   1:num/child-id <- start-running f2
-440   12:num <- copy 0  # race condition since we don't care about location 12
-441   # thanks to Scheduling_interval, f2's one instruction runs in between here and completes
-442   2:num/state <- routine-state 1:num/child-id
-443 ]
-444 def f2 [
-445   12:num <- copy 0
-446   # trying to run a second instruction marks routine as completed
-447 ]
-448 # recipe f2 should be in state COMPLETED
-449 +mem: storing 1 in location 2
-450 
-451 :(before "End Primitive Recipe Declarations")
-452 ROUTINE_STATE,
-453 :(before "End Primitive Recipe Numbers")
-454 put(Recipe_ordinal, "routine-state", ROUTINE_STATE);
-455 :(before "End Primitive Recipe Checks")
-456 case ROUTINE_STATE: {
-457   if (SIZE(inst.ingredients) != 1) {
-458   ¦ raise << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-459   ¦ break;
-460   }
-461   if (!is_mu_number(inst.ingredients.at(0))) {
-462   ¦ 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();
-463   ¦ break;
-464   }
-465   break;
-466 }
-467 :(before "End Primitive Recipe Implementations")
-468 case ROUTINE_STATE: {
-469   int id = ingredients.at(0).at(0);
-470   int result = -1;
-471   for (int i = 0;  i < SIZE(Routines);  ++i) {
-472   ¦ if (Routines.at(i)->id == id) {
-473   ¦ ¦ result = Routines.at(i)->state;
-474   ¦ ¦ break;
-475   ¦ }
-476   }
-477   products.resize(1);
-478   products.at(0).push_back(result);
-479   break;
-480 }
-481 
-482 //:: miscellaneous helpers
-483 
-484 :(before "End Primitive Recipe Declarations")
-485 STOP,
-486 :(before "End Primitive Recipe Numbers")
-487 put(Recipe_ordinal, "stop", STOP);
-488 :(before "End Primitive Recipe Checks")
-489 case STOP: {
-490   if (SIZE(inst.ingredients) != 1) {
-491   ¦ raise << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-492   ¦ break;
-493   }
-494   if (!is_mu_number(inst.ingredients.at(0))) {
-495   ¦ 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();
-496   ¦ break;
-497   }
-498   break;
-499 }
-500 :(before "End Primitive Recipe Implementations")
-501 case STOP: {
-502   int id = ingredients.at(0).at(0);
-503   for (int i = 0;  i < SIZE(Routines);  ++i) {
-504   ¦ if (Routines.at(i)->id == id) {
-505   ¦ ¦ Routines.at(i)->state = COMPLETED;
-506   ¦ ¦ break;
-507   ¦ }
-508   }
-509   break;
-510 }
-511 
-512 :(before "End Primitive Recipe Declarations")
-513 _DUMP_ROUTINES,
-514 :(before "End Primitive Recipe Numbers")
-515 put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES);
-516 :(before "End Primitive Recipe Checks")
-517 case _DUMP_ROUTINES: {
-518   break;
-519 }
-520 :(before "End Primitive Recipe Implementations")
-521 case _DUMP_ROUTINES: {
-522   for (int i = 0;  i < SIZE(Routines);  ++i) {
-523   ¦ cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n';
-524   }
-525   break;
-526 }
-527 
-528 //: support for stopping routines after some number of cycles
-529 
-530 :(scenario routine_discontinues_past_limit)
-531 % Scheduling_interval = 2;
-532 def f1 [
-533   1:num/child-id <- start-running f2
-534   limit-time 1:num/child-id, 10
-535   # padding loop just to make sure f2 has time to completed
-536   2:num <- copy 20
-537   2:num <- subtract 2:num, 1
-538   jump-if 2:num, -2:offset
-539 ]
-540 def f2 [
-541   jump -1:offset  # run forever
-542   $print [should never get here], 10/newline
-543 ]
-544 # f2 terminates
-545 +schedule: discontinuing routine 2
-546 
-547 :(before "End routine States")
-548 DISCONTINUED,
-549 :(before "End Scheduler State Transitions")
-550 if (Current_routine->limit >= 0) {
-551   if (Current_routine->limit <= Scheduling_interval) {
-552   ¦ trace(9999, "schedule") << "discontinuing routine " << Current_routine->id << end();
-553   ¦ Current_routine->state = DISCONTINUED;
-554   ¦ Current_routine->limit = 0;
-555   }
-556   else {
-557   ¦ Current_routine->limit -= Scheduling_interval;
-558   }
-559 }
-560 
-561 :(before "End Test Teardown")
-562 if (Passed && any_routines_with_error())
-563   raise << "some routines died with errors\n" << end();
-564 :(before "End Mu Test Teardown")
-565 if (Passed && any_routines_with_error())
-566   raise << Current_scenario->name << ": some routines died with errors\n" << end();
-567 
-568 :(code)
-569 bool any_routines_with_error() {
-570   for (int i = 0;  i < SIZE(Routines);  ++i) {
-571   ¦ if (Routines.at(i)->state == DISCONTINUED)
-572   ¦ ¦ return true;
-573   }
-574   return false;
-575 }
-576 
-577 :(before "End routine Fields")
-578 int limit;
-579 :(before "End routine Constructor")
-580 limit = -1;  /* no limit */
-581 
-582 :(before "End Primitive Recipe Declarations")
-583 LIMIT_TIME,
-584 :(before "End Primitive Recipe Numbers")
-585 put(Recipe_ordinal, "limit-time", LIMIT_TIME);
-586 :(before "End Primitive Recipe Checks")
-587 case LIMIT_TIME: {
-588   if (SIZE(inst.ingredients) != 2) {
-589   ¦ raise << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-590   ¦ break;
-591   }
-592   if (!is_mu_number(inst.ingredients.at(0))) {
-593   ¦ 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();
-594   ¦ break;
-595   }
-596   if (!is_mu_number(inst.ingredients.at(1))) {
-597   ¦ 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();
-598   ¦ break;
-599   }
-600   break;
-601 }
-602 :(before "End Primitive Recipe Implementations")
-603 case LIMIT_TIME: {
-604   int id = ingredients.at(0).at(0);
-605   for (int i = 0;  i < SIZE(Routines);  ++i) {
-606   ¦ if (Routines.at(i)->id == id) {
-607   ¦ ¦ Routines.at(i)->limit = ingredients.at(1).at(0);
-608   ¦ ¦ break;
-609   ¦ }
-610   }
-611   break;
-612 }
-613 
-614 :(before "End routine Fields")
-615 int instructions_run;
-616 :(before "End routine Constructor")
-617 instructions_run = 0;
-618 :(before "Reset instructions_run_this_scheduling_slice")
-619 Current_routine->instructions_run += Current_routine->instructions_run_this_scheduling_slice;
-620 :(before "End Primitive Recipe Declarations")
-621 NUMBER_OF_INSTRUCTIONS,
-622 :(before "End Primitive Recipe Numbers")
-623 put(Recipe_ordinal, "number-of-instructions", NUMBER_OF_INSTRUCTIONS);
-624 :(before "End Primitive Recipe Checks")
-625 case NUMBER_OF_INSTRUCTIONS: {
-626   if (SIZE(inst.ingredients) != 1) {
-627   ¦ raise << maybe(get(Recipe, r).name) << "'number-of-instructions' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-628   ¦ break;
-629   }
-630   if (!is_mu_number(inst.ingredients.at(0))) {
-631   ¦ 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();
-632   ¦ break;
-633   }
-634   break;
-635 }
-636 :(before "End Primitive Recipe Implementations")
-637 case NUMBER_OF_INSTRUCTIONS: {
-638   int id = ingredients.at(0).at(0);
-639   int result = -1;
-640   for (int i = 0;  i < SIZE(Routines);  ++i) {
-641   ¦ if (Routines.at(i)->id == id) {
-642   ¦ ¦ result = Routines.at(i)->instructions_run;
-643   ¦ ¦ break;
-644   ¦ }
-645   }
-646   products.resize(1);
-647   products.at(0).push_back(result);
-648   break;
-649 }
-650 
-651 :(scenario number_of_instructions)
-652 def f1 [
-653   10:num/child-id <- start-running f2
-654   {
-655   ¦ loop-unless 20:num
-656   }
-657   11:num <- number-of-instructions 10:num
-658 ]
-659 def f2 [
-660   # 2 instructions worth of work
-661   1:num <- copy 34
-662   20:num <- copy 1
-663 ]
-664 # f2 runs an extra instruction for the implicit return added by the
-665 # fill_in_return_ingredients transform
-666 +mem: storing 3 in location 11
-667 
-668 :(scenario number_of_instructions_across_multiple_scheduling_intervals)
-669 % Scheduling_interval = 1;
-670 def f1 [
-671   10:num/child-id <- start-running f2
-672   {
-673   ¦ loop-unless 20:num
-674   }
-675   11:num <- number-of-instructions 10:num
-676 ]
-677 def f2 [
-678   # 4 instructions worth of work
-679   1:num <- copy 34
-680   2:num <- copy 1
-681   2:num <- copy 3
-682   20:num <- copy 1
-683 ]
-684 # f2 runs an extra instruction for the implicit return added by the
-685 # fill_in_return_ingredients transform
-686 +mem: storing 5 in location 11
-687 
-688 //:: make sure that each routine gets a different alloc to start
-689 
-690 :(scenario new_concurrent)
-691 def f1 [
-692   start-running f2
-693   1:&:num/raw <- new number:type
-694   # wait for f2 to complete
-695   {
-696   ¦ loop-unless 4:num/raw
-697   }
-698 ]
-699 def f2 [
-700   2:&:num/raw <- new number:type
-701   # hack: assumes scheduler implementation
-702   3:bool/raw <- equal 1:&:num/raw, 2:&:num/raw
-703   # signal f2 complete
-704   4:num/raw <- copy 1
-705 ]
-706 +mem: storing 0 in location 3
-
- - - diff --git a/html/073scheduler.cc.html b/html/073scheduler.cc.html new file mode 100644 index 00000000..dc482071 --- /dev/null +++ b/html/073scheduler.cc.html @@ -0,0 +1,761 @@ + + + + +Mu - 073scheduler.cc + + + + + + + + + + +
+  1 //: Run a second routine concurrently using 'start-running', without any
+  2 //: guarantees on how the operations in each are interleaved with each other.
+  3 
+  4 :(scenario scheduler)
+  5 def f1 [
+  6   start-running f2
+  7   # wait for f2 to run
+  8   {
+  9   ¦ jump-unless 1:num, -1
+ 10   }
+ 11 ]
+ 12 def f2 [
+ 13   1:num <- copy 1
+ 14 ]
+ 15 +schedule: f1
+ 16 +schedule: f2
+ 17 
+ 18 //: first, add a deadline to run(routine)
+ 19 :(before "End Globals")
+ 20 int Scheduling_interval = 500;
+ 21 :(before "End routine Fields")
+ 22 int instructions_run_this_scheduling_slice;
+ 23 :(before "End routine Constructor")
+ 24 instructions_run_this_scheduling_slice = 0;
+ 25 :(after "Running One Instruction")
+ 26  ++Current_routine->instructions_run_this_scheduling_slice;
+ 27 :(replace{} "bool should_continue_running(const routine* current_routine)")
+ 28 bool should_continue_running(const routine* current_routine) {
+ 29   assert(current_routine == Current_routine);  // argument passed in just to make caller readable above
+ 30   return Current_routine->state == RUNNING
+ 31   ¦ ¦ && Current_routine->instructions_run_this_scheduling_slice < Scheduling_interval;
+ 32 }
+ 33 :(after "stop_running_current_routine:")
+ 34 // Reset instructions_run_this_scheduling_slice
+ 35 Current_routine->instructions_run_this_scheduling_slice = 0;
+ 36 
+ 37 //: now the rest of the scheduler is clean
+ 38 
+ 39 :(before "struct routine")
+ 40 enum routine_state {
+ 41   RUNNING,
+ 42   COMPLETED,
+ 43   // End routine States
+ 44 };
+ 45 :(before "End routine Fields")
+ 46 enum routine_state state;
+ 47 :(before "End routine Constructor")
+ 48 state = RUNNING;
+ 49 
+ 50 :(before "End Globals")
+ 51 vector<routine*> Routines;
+ 52 int Current_routine_index = 0;
+ 53 :(before "End Reset")
+ 54 Scheduling_interval = 500;
+ 55 for (int i = 0;  i < SIZE(Routines);  ++i)
+ 56   delete Routines.at(i);
+ 57 Routines.clear();
+ 58 Current_routine = NULL;
+ 59 :(replace{} "void run(const recipe_ordinal r)")
+ 60 void run(const recipe_ordinal r) {
+ 61   run(new routine(r));
+ 62 }
+ 63 
+ 64 :(code)
+ 65 void run(routine* rr) {
+ 66   Routines.push_back(rr);
+ 67   Current_routine_index = 0, Current_routine = Routines.at(0);
+ 68   while (!all_routines_done()) {
+ 69   ¦ skip_to_next_routine();
+ 70   ¦ assert(Current_routine);
+ 71   ¦ assert(Current_routine->state == RUNNING);
+ 72   ¦ trace(9990, "schedule") << current_routine_label() << end();
+ 73   ¦ run_current_routine();
+ 74   ¦ // Scheduler State Transitions
+ 75   ¦ if (Current_routine->completed())
+ 76   ¦ ¦ Current_routine->state = COMPLETED;
+ 77   ¦ // End Scheduler State Transitions
+ 78 
+ 79   ¦ // Scheduler Cleanup
+ 80   ¦ // End Scheduler Cleanup
+ 81   }
+ 82   // End Run Routine
+ 83 }
+ 84 
+ 85 bool all_routines_done() {
+ 86   for (int i = 0;  i < SIZE(Routines);  ++i) {
+ 87   ¦ if (Routines.at(i)->state == RUNNING)
+ 88   ¦ ¦ return false;
+ 89   }
+ 90   return true;
+ 91 }
+ 92 
+ 93 // skip Current_routine_index past non-RUNNING routines
+ 94 void skip_to_next_routine() {
+ 95   assert(!Routines.empty());
+ 96   assert(Current_routine_index < SIZE(Routines));
+ 97   for (int i = (Current_routine_index+1)%SIZE(Routines);  i != Current_routine_index;  i = (i+1)%SIZE(Routines)) {
+ 98   ¦ if (Routines.at(i)->state == RUNNING) {
+ 99   ¦ ¦ Current_routine_index = i;
+100   ¦ ¦ Current_routine = Routines.at(i);
+101   ¦ ¦ return;
+102   ¦ }
+103   }
+104 }
+105 
+106 string current_routine_label() {
+107   return routine_label(Current_routine);
+108 }
+109 
+110 string routine_label(routine* r) {
+111   ostringstream result;
+112   const call_stack& calls = r->calls;
+113   for (call_stack::const_iterator p = calls.begin();  p != calls.end();  ++p) {
+114   ¦ if (p != calls.begin()) result << '/';
+115   ¦ result << get(Recipe, p->running_recipe).name;
+116   }
+117   return result.str();
+118 }
+119 
+120 //: special case for the very first routine
+121 :(replace{} "void run_main(int argc, char* argv[])")
+122 void run_main(int argc, char* argv[]) {
+123   recipe_ordinal r = get(Recipe_ordinal, "main");
+124   assert(r);
+125   routine* main_routine = new routine(r);
+126   // pass in commandline args as ingredients to main
+127   // todo: test this
+128   Current_routine = main_routine;
+129   for (int i = 1;  i < argc;  ++i) {
+130   ¦ vector<double> arg;
+131   ¦ arg.push_back(new_mu_text(argv[i]));
+132   ¦ assert(get(Memory, arg.back()) == 0);
+133   ¦ put(Memory, arg.back(), 1);  // update refcount
+134   ¦ current_call().ingredient_atoms.push_back(arg);
+135   }
+136   run(main_routine);
+137 }
+138 
+139 //:: To schedule new routines to run, call 'start-running'.
+140 
+141 //: 'start-running' will return a unique id for the routine that was created.
+142 //: routine id is a number, but don't do any arithmetic on it
+143 :(before "End routine Fields")
+144 int id;
+145 :(before "End Globals")
+146 int Next_routine_id = 1;
+147 :(before "End Reset")
+148 Next_routine_id = 1;
+149 :(before "End routine Constructor")
+150 id = Next_routine_id;
+151 ++Next_routine_id;
+152 
+153 //: routines save the routine that spawned them
+154 :(before "End routine Fields")
+155 // todo: really should be routine_id, but that's less efficient.
+156 int parent_index;  // only < 0 if there's no parent_index
+157 :(before "End routine Constructor")
+158 parent_index = -1;
+159 
+160 :(before "End Primitive Recipe Declarations")
+161 START_RUNNING,
+162 :(before "End Primitive Recipe Numbers")
+163 put(Recipe_ordinal, "start-running", START_RUNNING);
+164 :(before "End Primitive Recipe Checks")
+165 case START_RUNNING: {
+166   if (inst.ingredients.empty()) {
+167   ¦ raise << maybe(get(Recipe, r).name) << "'start-running' requires at least one ingredient: the recipe to start running\n" << end();
+168   ¦ break;
+169   }
+170   if (!is_mu_recipe(inst.ingredients.at(0))) {
+171   ¦ 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();
+172   ¦ break;
+173   }
+174   break;
+175 }
+176 :(before "End Primitive Recipe Implementations")
+177 case START_RUNNING: {
+178   routine* new_routine = new routine(ingredients.at(0).at(0));
+179   new_routine->parent_index = Current_routine_index;
+180   // populate ingredients
+181   for (int i = /*skip callee*/1;  i < SIZE(current_instruction().ingredients);  ++i) {
+182   ¦ reagent/*copy*/ ingredient = current_instruction().ingredients.at(i);
+183   ¦ new_routine->calls.front().ingredients.push_back(ingredient);
+184   ¦ vector<double> new_ingredient_atoms = deep_copy(ingredient);
+185   ¦ new_routine->calls.front().ingredient_atoms.push_back(new_ingredient_atoms);
+186   ¦ // End Populate start-running Ingredient
+187   }
+188   Routines.push_back(new_routine);
+189   products.resize(1);
+190   products.at(0).push_back(new_routine->id);
+191   break;
+192 }
+193 
+194 :(scenario scheduler_runs_single_routine)
+195 % Scheduling_interval = 1;
+196 def f1 [
+197   1:num <- copy 0
+198   2:num <- copy 0
+199 ]
+200 +schedule: f1
+201 +run: {1: "number"} <- copy {0: "literal"}
+202 +schedule: f1
+203 +run: {2: "number"} <- copy {0: "literal"}
+204 
+205 :(scenario scheduler_interleaves_routines)
+206 % Scheduling_interval = 1;
+207 def f1 [
+208   start-running f2
+209   1:num <- copy 0
+210   2:num <- copy 0
+211 ]
+212 def f2 [
+213   3:num <- copy 0
+214   4:num <- copy 0
+215 ]
+216 +schedule: f1
+217 +run: start-running {f2: "recipe-literal"}
+218 +schedule: f2
+219 +run: {3: "number"} <- copy {0: "literal"}
+220 +schedule: f1
+221 +run: {1: "number"} <- copy {0: "literal"}
+222 +schedule: f2
+223 +run: {4: "number"} <- copy {0: "literal"}
+224 +schedule: f1
+225 +run: {2: "number"} <- copy {0: "literal"}
+226 
+227 :(scenario start_running_takes_ingredients)
+228 def f1 [
+229   start-running f2, 3
+230   # wait for f2 to run
+231   {
+232   ¦ jump-unless 1:num, -1
+233   }
+234 ]
+235 def f2 [
+236   1:num <- next-ingredient
+237   2:num <- add 1:num, 1
+238 ]
+239 +mem: storing 4 in location 2
+240 
+241 //: type-checking for 'start-running'
+242 
+243 :(scenario start_running_checks_types)
+244 % Hide_errors = true;
+245 def f1 [
+246   start-running f2, 3
+247 ]
+248 def f2 n:&:num [
+249 ]
+250 +error: f1: ingredient 0 has the wrong type at 'start-running f2, 3'
+251 
+252 // 'start-running' only uses the ingredients of the callee, not its products
+253 :(before "End is_indirect_call_with_ingredients Special-cases")
+254 if (r == START_RUNNING) return true;
+255 
+256 //: refcounting management when starting up new routines
+257 
+258 :(scenario start_running_immediately_updates_refcounts_of_ingredients)
+259 % Scheduling_interval = 1;
+260 def main [
+261   local-scope
+262   create-new-routine
+263   # padding to make sure we run new-routine before returning
+264   dummy:num <- copy 0
+265   dummy:num <- copy 0
+266 ]
+267 def create-new-routine [
+268   local-scope
+269   n:&:num <- new number:type
+270   *n <- copy 34
+271   start-running new-routine, n
+272   # refcount of n decremented
+273 ]
+274 def new-routine n:&:num [
+275   local-scope
+276   load-ingredients
+277   1:num/raw <- copy *n
+278 ]
+279 # check that n was successfully passed into new-routine before being reclaimed
+280 +mem: storing 34 in location 1
+281 
+282 //: ensure this works with indirect calls using 'call' as well
+283 :(scenario start_running_immediately_updates_refcounts_of_ingredients_of_indirect_calls)
+284 % Scheduling_interval = 1;
+285 def main [
+286   local-scope
+287   n:&:num <- new number:type
+288   *n <- copy 34
+289   call f1, n
+290   1:num/raw <- copy *n
+291 ]
+292 def f1 n:&:num [
+293   local-scope
+294   load-ingredients
+295 ]
+296 # check that n was successfully passed into new-routine before being reclaimed
+297 +mem: storing 34 in location 1
+298 
+299 :(scenario next_ingredient_never_leaks_refcounts)
+300 def create-space n:&:num -> default-space:space [
+301   default-space <- new location:type, 2
+302   load-ingredients
+303 ]
+304 def use-space [
+305   local-scope
+306   0:space/names:create-space <- next-ingredient
+307   n:&:num/space:1 <- next-ingredient  # should decrement refcount
+308   *n/space:1 <- copy 34
+309   n2:num <- add *n/space:1, 1
+310   return n2
+311 ]
+312 def main [
+313   local-scope
+314   n:&:num <- copy 12000/unsafe  # pretend allocation with a known address
+315   *n <- copy 23
+316   space:space <- create-space n
+317   n2:&:num <- copy 13000/unsafe
+318   n3:num <- use-space space, n2
+319 ]
+320 +run: {n: ("address" "number"), "space": "1"} <- next-ingredient
+321 +mem: decrementing refcount of 12000: 2 -> 1
+322 +run: {n: ("address" "number"), "space": "1", "lookup": ()} <- copy {34: "literal"}
+323 
+324 //: back to testing 'start-running'
+325 
+326 :(scenario start_running_returns_routine_id)
+327 def f1 [
+328   1:num <- start-running f2
+329 ]
+330 def f2 [
+331   12:num <- copy 44
+332 ]
+333 +mem: storing 2 in location 1
+334 
+335 //: this scenario will require some careful setup in escaped C++
+336 //: (straining our tangle capabilities to near-breaking point)
+337 :(scenario scheduler_skips_completed_routines)
+338 % recipe_ordinal f1 = load("recipe f1 [\n1:num <- copy 0\n]\n").front();
+339 % recipe_ordinal f2 = load("recipe f2 [\n2:num <- copy 0\n]\n").front();
+340 % Routines.push_back(new routine(f1));  // f1 meant to run
+341 % Routines.push_back(new routine(f2));
+342 % Routines.back()->state = COMPLETED;  // f2 not meant to run
+343 # must have at least one routine without escaping
+344 def f3 [
+345   3:num <- copy 0
+346 ]
+347 # by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order
+348 +schedule: f1
+349 +mem: storing 0 in location 1
+350 -schedule: f2
+351 -mem: storing 0 in location 2
+352 +schedule: f3
+353 +mem: storing 0 in location 3
+354 
+355 :(scenario scheduler_starts_at_middle_of_routines)
+356 % Routines.push_back(new routine(COPY));
+357 % Routines.back()->state = COMPLETED;
+358 def f1 [
+359   1:num <- copy 0
+360   2:num <- copy 0
+361 ]
+362 +schedule: f1
+363 -run: idle
+364 
+365 //:: Errors in a routine cause it to terminate.
+366 
+367 :(scenario scheduler_terminates_routines_after_errors)
+368 % Hide_errors = true;
+369 % Scheduling_interval = 2;
+370 def f1 [
+371   start-running f2
+372   1:num <- copy 0
+373   2:num <- copy 0
+374 ]
+375 def f2 [
+376   # divide by 0 twice
+377   3:num <- divide-with-remainder 4, 0
+378   4:num <- divide-with-remainder 4, 0
+379 ]
+380 # f2 should stop after first divide by 0
+381 +error: f2: divide by zero in '3:num <- divide-with-remainder 4, 0'
+382 -error: f2: divide by zero in '4:num <- divide-with-remainder 4, 0'
+383 
+384 :(after "operator<<(ostream& os, unused end)")
+385   if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) {
+386   ¦ Current_routine->state = COMPLETED;
+387   }
+388 
+389 //:: Routines are marked completed when their parent completes.
+390 
+391 :(scenario scheduler_kills_orphans)
+392 def main [
+393   start-running f1
+394   # f1 never actually runs because its parent completes without waiting for it
+395 ]
+396 def f1 [
+397   1:num <- copy 0
+398 ]
+399 -schedule: f1
+400 
+401 :(before "End Scheduler Cleanup")
+402 for (int i = 0;  i < SIZE(Routines);  ++i) {
+403   if (Routines.at(i)->state == COMPLETED) continue;
+404   if (Routines.at(i)->parent_index < 0) continue;  // root thread
+405   // structured concurrency: http://250bpm.com/blog:71
+406   if (has_completed_parent(i)) {
+407   ¦ Routines.at(i)->state = COMPLETED;
+408   }
+409 }
+410 
+411 :(code)
+412 bool has_completed_parent(int routine_index) {
+413   for (int j = routine_index;  j >= 0;  j = Routines.at(j)->parent_index) {
+414   ¦ if (Routines.at(j)->state == COMPLETED)
+415   ¦ ¦ return true;
+416   }
+417   return false;
+418 }
+419 
+420 //:: 'routine-state' can tell if a given routine id is running
+421 
+422 :(scenario routine_state_test)
+423 % Scheduling_interval = 2;
+424 def f1 [
+425   1:num/child-id <- start-running f2
+426   12:num <- copy 0  # race condition since we don't care about location 12
+427   # thanks to Scheduling_interval, f2's one instruction runs in between here and completes
+428   2:num/state <- routine-state 1:num/child-id
+429 ]
+430 def f2 [
+431   12:num <- copy 0
+432   # trying to run a second instruction marks routine as completed
+433 ]
+434 # recipe f2 should be in state COMPLETED
+435 +mem: storing 1 in location 2
+436 
+437 :(before "End Primitive Recipe Declarations")
+438 ROUTINE_STATE,
+439 :(before "End Primitive Recipe Numbers")
+440 put(Recipe_ordinal, "routine-state", ROUTINE_STATE);
+441 :(before "End Primitive Recipe Checks")
+442 case ROUTINE_STATE: {
+443   if (SIZE(inst.ingredients) != 1) {
+444   ¦ raise << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+445   ¦ break;
+446   }
+447   if (!is_mu_number(inst.ingredients.at(0))) {
+448   ¦ 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();
+449   ¦ break;
+450   }
+451   break;
+452 }
+453 :(before "End Primitive Recipe Implementations")
+454 case ROUTINE_STATE: {
+455   int id = ingredients.at(0).at(0);
+456   int result = -1;
+457   for (int i = 0;  i < SIZE(Routines);  ++i) {
+458   ¦ if (Routines.at(i)->id == id) {
+459   ¦ ¦ result = Routines.at(i)->state;
+460   ¦ ¦ break;
+461   ¦ }
+462   }
+463   products.resize(1);
+464   products.at(0).push_back(result);
+465   break;
+466 }
+467 
+468 //:: miscellaneous helpers
+469 
+470 :(before "End Primitive Recipe Declarations")
+471 STOP,
+472 :(before "End Primitive Recipe Numbers")
+473 put(Recipe_ordinal, "stop", STOP);
+474 :(before "End Primitive Recipe Checks")
+475 case STOP: {
+476   if (SIZE(inst.ingredients) != 1) {
+477   ¦ raise << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+478   ¦ break;
+479   }
+480   if (!is_mu_number(inst.ingredients.at(0))) {
+481   ¦ 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();
+482   ¦ break;
+483   }
+484   break;
+485 }
+486 :(before "End Primitive Recipe Implementations")
+487 case STOP: {
+488   int id = ingredients.at(0).at(0);
+489   for (int i = 0;  i < SIZE(Routines);  ++i) {
+490   ¦ if (Routines.at(i)->id == id) {
+491   ¦ ¦ Routines.at(i)->state = COMPLETED;
+492   ¦ ¦ break;
+493   ¦ }
+494   }
+495   break;
+496 }
+497 
+498 :(before "End Primitive Recipe Declarations")
+499 _DUMP_ROUTINES,
+500 :(before "End Primitive Recipe Numbers")
+501 put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES);
+502 :(before "End Primitive Recipe Checks")
+503 case _DUMP_ROUTINES: {
+504   break;
+505 }
+506 :(before "End Primitive Recipe Implementations")
+507 case _DUMP_ROUTINES: {
+508   for (int i = 0;  i < SIZE(Routines);  ++i) {
+509   ¦ cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n';
+510   }
+511   break;
+512 }
+513 
+514 //: support for stopping routines after some number of cycles
+515 
+516 :(scenario routine_discontinues_past_limit)
+517 % Scheduling_interval = 2;
+518 def f1 [
+519   1:num/child-id <- start-running f2
+520   limit-time 1:num/child-id, 10
+521   # padding loop just to make sure f2 has time to completed
+522   2:num <- copy 20
+523   2:num <- subtract 2:num, 1
+524   jump-if 2:num, -2:offset
+525 ]
+526 def f2 [
+527   jump -1:offset  # run forever
+528   $print [should never get here], 10/newline
+529 ]
+530 # f2 terminates
+531 +schedule: discontinuing routine 2
+532 
+533 :(before "End routine States")
+534 DISCONTINUED,
+535 :(before "End Scheduler State Transitions")
+536 if (Current_routine->limit >= 0) {
+537   if (Current_routine->limit <= Scheduling_interval) {
+538   ¦ trace(9999, "schedule") << "discontinuing routine " << Current_routine->id << end();
+539   ¦ Current_routine->state = DISCONTINUED;
+540   ¦ Current_routine->limit = 0;
+541   }
+542   else {
+543   ¦ Current_routine->limit -= Scheduling_interval;
+544   }
+545 }
+546 
+547 :(before "End Test Teardown")
+548 if (Passed && any_routines_with_error())
+549   raise << "some routines died with errors\n" << end();
+550 :(before "End Mu Test Teardown")
+551 if (Passed && any_routines_with_error())
+552   raise << Current_scenario->name << ": some routines died with errors\n" << end();
+553 
+554 :(code)
+555 bool any_routines_with_error() {
+556   for (int i = 0;  i < SIZE(Routines);  ++i) {
+557   ¦ if (Routines.at(i)->state == DISCONTINUED)
+558   ¦ ¦ return true;
+559   }
+560   return false;
+561 }
+562 
+563 :(before "End routine Fields")
+564 int limit;
+565 :(before "End routine Constructor")
+566 limit = -1;  /* no limit */
+567 
+568 :(before "End Primitive Recipe Declarations")
+569 LIMIT_TIME,
+570 :(before "End Primitive Recipe Numbers")
+571 put(Recipe_ordinal, "limit-time", LIMIT_TIME);
+572 :(before "End Primitive Recipe Checks")
+573 case LIMIT_TIME: {
+574   if (SIZE(inst.ingredients) != 2) {
+575   ¦ raise << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+576   ¦ break;
+577   }
+578   if (!is_mu_number(inst.ingredients.at(0))) {
+579   ¦ 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();
+580   ¦ break;
+581   }
+582   if (!is_mu_number(inst.ingredients.at(1))) {
+583   ¦ 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();
+584   ¦ break;
+585   }
+586   break;
+587 }
+588 :(before "End Primitive Recipe Implementations")
+589 case LIMIT_TIME: {
+590   int id = ingredients.at(0).at(0);
+591   for (int i = 0;  i < SIZE(Routines);  ++i) {
+592   ¦ if (Routines.at(i)->id == id) {
+593   ¦ ¦ Routines.at(i)->limit = ingredients.at(1).at(0);
+594   ¦ ¦ break;
+595   ¦ }
+596   }
+597   break;
+598 }
+599 
+600 :(before "End routine Fields")
+601 int instructions_run;
+602 :(before "End routine Constructor")
+603 instructions_run = 0;
+604 :(before "Reset instructions_run_this_scheduling_slice")
+605 Current_routine->instructions_run += Current_routine->instructions_run_this_scheduling_slice;
+606 :(before "End Primitive Recipe Declarations")
+607 NUMBER_OF_INSTRUCTIONS,
+608 :(before "End Primitive Recipe Numbers")
+609 put(Recipe_ordinal, "number-of-instructions", NUMBER_OF_INSTRUCTIONS);
+610 :(before "End Primitive Recipe Checks")
+611 case NUMBER_OF_INSTRUCTIONS: {
+612   if (SIZE(inst.ingredients) != 1) {
+613   ¦ raise << maybe(get(Recipe, r).name) << "'number-of-instructions' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+614   ¦ break;
+615   }
+616   if (!is_mu_number(inst.ingredients.at(0))) {
+617   ¦ 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();
+618   ¦ break;
+619   }
+620   break;
+621 }
+622 :(before "End Primitive Recipe Implementations")
+623 case NUMBER_OF_INSTRUCTIONS: {
+624   int id = ingredients.at(0).at(0);
+625   int result = -1;
+626   for (int i = 0;  i < SIZE(Routines);  ++i) {
+627   ¦ if (Routines.at(i)->id == id) {
+628   ¦ ¦ result = Routines.at(i)->instructions_run;
+629   ¦ ¦ break;
+630   ¦ }
+631   }
+632   products.resize(1);
+633   products.at(0).push_back(result);
+634   break;
+635 }
+636 
+637 :(scenario number_of_instructions)
+638 def f1 [
+639   10:num/child-id <- start-running f2
+640   {
+641   ¦ loop-unless 20:num
+642   }
+643   11:num <- number-of-instructions 10:num
+644 ]
+645 def f2 [
+646   # 2 instructions worth of work
+647   1:num <- copy 34
+648   20:num <- copy 1
+649 ]
+650 # f2 runs an extra instruction for the implicit return added by the
+651 # fill_in_return_ingredients transform
+652 +mem: storing 3 in location 11
+653 
+654 :(scenario number_of_instructions_across_multiple_scheduling_intervals)
+655 % Scheduling_interval = 1;
+656 def f1 [
+657   10:num/child-id <- start-running f2
+658   {
+659   ¦ loop-unless 20:num
+660   }
+661   11:num <- number-of-instructions 10:num
+662 ]
+663 def f2 [
+664   # 4 instructions worth of work
+665   1:num <- copy 34
+666   2:num <- copy 1
+667   2:num <- copy 3
+668   20:num <- copy 1
+669 ]
+670 # f2 runs an extra instruction for the implicit return added by the
+671 # fill_in_return_ingredients transform
+672 +mem: storing 5 in location 11
+673 
+674 //:: make sure that each routine gets a different alloc to start
+675 
+676 :(scenario new_concurrent)
+677 def f1 [
+678   start-running f2
+679   1:&:num/raw <- new number:type
+680   # wait for f2 to complete
+681   {
+682   ¦ loop-unless 4:num/raw
+683   }
+684 ]
+685 def f2 [
+686   2:&:num/raw <- new number:type
+687   # hack: assumes scheduler implementation
+688   3:bool/raw <- equal 1:&:num/raw, 2:&:num/raw
+689   # signal f2 complete
+690   4:num/raw <- copy 1
+691 ]
+692 +mem: storing 0 in location 3
+
+ + + diff --git a/html/073wait.cc.html b/html/073wait.cc.html deleted file mode 100644 index 2a08a20a..00000000 --- a/html/073wait.cc.html +++ /dev/null @@ -1,670 +0,0 @@ - - - - -Mu - 073wait.cc - - - - - - - - - - -
-  1 //: Routines can be put in a 'waiting' state, from which it will be ready to
-  2 //: run again when a specific memory location changes its value. This is Mu's
-  3 //: basic technique for orchestrating the order in which different routines
-  4 //: operate.
-  5 
-  6 :(scenario wait_for_location)
-  7 def f1 [
-  8   10:num <- copy 34
-  9   start-running f2
- 10   20:location <- copy 10/unsafe
- 11   wait-for-reset-then-set 20:location
- 12   # wait for f2 to run and reset location 1
- 13   30:num <- copy 10:num
- 14 ]
- 15 def f2 [
- 16   10:location <- copy 0/unsafe
- 17 ]
- 18 +schedule: f1
- 19 +run: waiting for location 10 to reset
- 20 +schedule: f2
- 21 +schedule: waking up routine 1
- 22 +schedule: f1
- 23 +mem: storing 1 in location 30
- 24 
- 25 //: define the new state that all routines can be in
- 26 
- 27 :(before "End routine States")
- 28 WAITING,
- 29 :(before "End routine Fields")
- 30 // only if state == WAITING
- 31 int waiting_on_location;
- 32 :(before "End routine Constructor")
- 33 waiting_on_location = 0;
- 34 
- 35 :(before "End Mu Test Teardown")
- 36 if (Passed && any_routines_waiting())
- 37   raise << Current_scenario->name << ": deadlock!\n" << end();
- 38 :(before "End Run Routine")
- 39 if (any_routines_waiting()) {
- 40   raise << "deadlock!\n" << end();
- 41   dump_waiting_routines();
- 42 }
- 43 :(before "End Test Teardown")
- 44 if (Passed && any_routines_with_error())
- 45   raise << "some routines died with errors\n" << end();
- 46 :(code)
- 47 bool any_routines_waiting() {
- 48   for (int i = 0;  i < SIZE(Routines);  ++i) {
- 49   ¦ if (Routines.at(i)->state == WAITING)
- 50   ¦ ¦ return true;
- 51   }
- 52   return false;
- 53 }
- 54 void dump_waiting_routines() {
- 55   for (int i = 0;  i < SIZE(Routines);  ++i) {
- 56   ¦ if (Routines.at(i)->state == WAITING)
- 57   ¦ ¦ cerr << i << ": " << routine_label(Routines.at(i)) << '\n';
- 58   }
- 59 }
- 60 
- 61 :(scenario wait_for_location_can_deadlock)
- 62 % Hide_errors = true;
- 63 def main [
- 64   10:num <- copy 1
- 65   20:location <- copy 10/unsafe
- 66   wait-for-reset-then-set 20:location
- 67 ]
- 68 +error: deadlock!
- 69 
- 70 //: Primitive recipe to put routines in that state.
- 71 //: This primitive is also known elsewhere as compare-and-set (CAS). Used to
- 72 //: build locks.
- 73 
- 74 :(before "End Primitive Recipe Declarations")
- 75 WAIT_FOR_RESET_THEN_SET,
- 76 :(before "End Primitive Recipe Numbers")
- 77 put(Recipe_ordinal, "wait-for-reset-then-set", WAIT_FOR_RESET_THEN_SET);
- 78 :(before "End Primitive Recipe Checks")
- 79 case WAIT_FOR_RESET_THEN_SET: {
- 80   if (SIZE(inst.ingredients) != 1) {
- 81   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
- 82   ¦ break;
- 83   }
- 84   if (!is_mu_location(inst.ingredients.at(0))) {
- 85   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
- 86   }
- 87   break;
- 88 }
- 89 :(before "End Primitive Recipe Implementations")
- 90 case WAIT_FOR_RESET_THEN_SET: {
- 91   int loc = static_cast<int>(ingredients.at(0).at(0));
- 92   trace(9998, "run") << "wait: *" << loc << " = " << get_or_insert(Memory, loc) << end();
- 93   if (get_or_insert(Memory, loc) == 0) {
- 94   ¦ trace(9998, "run") << "location " << loc << " is already 0; setting" << end();
- 95   ¦ put(Memory, loc, 1);
- 96   ¦ break;
- 97   }
- 98   trace(9998, "run") << "waiting for location " << loc << " to reset" << end();
- 99   Current_routine->state = WAITING;
-100   Current_routine->waiting_on_location = loc;
-101   break;
-102 }
-103 
-104 //: Counterpart to unlock a lock.
-105 :(before "End Primitive Recipe Declarations")
-106 RESET,
-107 :(before "End Primitive Recipe Numbers")
-108 put(Recipe_ordinal, "reset", RESET);
-109 :(before "End Primitive Recipe Checks")
-110 case RESET: {
-111   if (SIZE(inst.ingredients) != 1) {
-112   ¦ raise << maybe(get(Recipe, r).name) << "'reset' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-113   ¦ break;
-114   }
-115   if (!is_mu_location(inst.ingredients.at(0))) {
-116   ¦ raise << maybe(get(Recipe, r).name) << "'reset' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
-117   }
-118   break;
-119 }
-120 :(before "End Primitive Recipe Implementations")
-121 case RESET: {
-122   int loc = static_cast<int>(ingredients.at(0).at(0));
-123   put(Memory, loc, 0);
-124   trace(9998, "run") << "reset: *" << loc << " = " << get_or_insert(Memory, loc) << end();
-125   break;
-126 }
-127 
-128 //: scheduler tweak to get routines out of that state
-129 
-130 :(before "End Scheduler State Transitions")
-131 for (int i = 0;  i < SIZE(Routines);  ++i) {
-132   if (Routines.at(i)->state != WAITING) continue;
-133   int loc = Routines.at(i)->waiting_on_location;
-134   if (loc && get_or_insert(Memory, loc) == 0) {
-135   ¦ trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end();
-136   ¦ put(Memory, loc, 1);
-137   ¦ Routines.at(i)->state = RUNNING;
-138   ¦ Routines.at(i)->waiting_on_location = 0;
-139   }
-140 }
-141 
-142 //: Primitive to help compute locations to wait on.
-143 //: Only supports elements immediately inside containers; no arrays or
-144 //: containers within containers yet.
-145 
-146 :(scenario get_location)
-147 def main [
-148   12:num <- copy 34
-149   13:num <- copy 35
-150   15:location <- get-location 12:point, 1:offset
-151 ]
-152 +mem: storing 13 in location 15
-153 
-154 :(before "End Primitive Recipe Declarations")
-155 GET_LOCATION,
-156 :(before "End Primitive Recipe Numbers")
-157 put(Recipe_ordinal, "get-location", GET_LOCATION);
-158 :(before "End Primitive Recipe Checks")
-159 case GET_LOCATION: {
-160   if (SIZE(inst.ingredients) != 2) {
-161   ¦ raise << maybe(get(Recipe, r).name) << "'get-location' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end();
-162   ¦ break;
-163   }
-164   reagent/*copy*/ base = inst.ingredients.at(0);
-165   if (!canonize_type(base)) break;
-166   if (!base.type) {
-167   ¦ 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();
-168   ¦ break;
-169   }
-170   const type_tree* base_root_type = base.type->atom ? base.type : base.type->left;
-171   if (!base_root_type->atom || base_root_type->value == 0 || !contains_key(Type, base_root_type->value) || get(Type, base_root_type->value).kind != CONTAINER) {
-172   ¦ 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();
-173   ¦ break;
-174   }
-175   type_ordinal base_type = base.type->value;
-176   const reagent& offset = inst.ingredients.at(1);
-177   if (!is_literal(offset) || !is_mu_scalar(offset)) {
-178   ¦ 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();
-179   ¦ break;
-180   }
-181   int offset_value = 0;
-182   //: later layers will permit non-integer offsets
-183   if (is_integer(offset.name)) {
-184   ¦ offset_value = to_integer(offset.name);
-185   ¦ if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) {
-186   ¦ ¦ raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for '" << get(Type, base_type).name << "'\n" << end();
-187   ¦ ¦ break;
-188   ¦ }
-189   }
-190   else {
-191   ¦ offset_value = offset.value;
-192   }
-193   if (inst.products.empty()) break;
-194   if (!is_mu_location(inst.products.at(0))) {
-195   ¦ 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();
-196   ¦ break;
-197   }
-198   break;
-199 }
-200 :(before "End Primitive Recipe Implementations")
-201 case GET_LOCATION: {
-202   reagent/*copy*/ base = current_instruction().ingredients.at(0);
-203   canonize(base);
-204   int base_address = base.value;
-205   if (base_address == 0) {
-206   ¦ raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end();
-207   ¦ break;
-208   }
-209   const type_tree* base_type = get_base_type(base.type);
-210   int offset = ingredients.at(1).at(0);
-211   if (offset < 0 || offset >= SIZE(get(Type, base_type->value).elements)) break;  // copied from Check above
-212   int result = base_address;
-213   for (int i = 0;  i < offset;  ++i)
-214   ¦ result += size_of(element_type(base.type, i));
-215   trace(9998, "run") << "address to copy is " << result << end();
-216   products.resize(1);
-217   products.at(0).push_back(result);
-218   break;
-219 }
-220 
-221 :(code)
-222 bool is_mu_location(reagent/*copy*/ x) {
-223   if (!canonize_type(x)) return false;
-224   if (!x.type) return false;
-225   if (!x.type->atom) return false;
-226   return x.type->value == get(Type_ordinal, "location");
-227 }
-228 
-229 :(scenario get_location_out_of_bounds)
-230 % Hide_errors = true;
-231 def main [
-232   12:num <- copy 34
-233   13:num <- copy 35
-234   14:num <- copy 36
-235   get-location 12:point-number/raw, 2:offset  # point-number occupies 3 locations but has only 2 fields; out of bounds
-236 ]
-237 +error: main: invalid offset 2 for 'point-number'
-238 
-239 :(scenario get_location_out_of_bounds_2)
-240 % Hide_errors = true;
-241 def main [
-242   12:num <- copy 34
-243   13:num <- copy 35
-244   14:num <- copy 36
-245   get-location 12:point-number/raw, -1:offset
-246 ]
-247 +error: main: invalid offset -1 for 'point-number'
-248 
-249 :(scenario get_location_product_type_mismatch)
-250 % Hide_errors = true;
-251 container boolbool [
-252   x:bool
-253   y:bool
-254 ]
-255 def main [
-256   12:bool <- copy 1
-257   13:bool <- copy 0
-258   15:bool <- get-location 12:boolbool, 1:offset
-259 ]
-260 +error: main: 'get-location 12:boolbool, 1:offset' should write to type location but '15' has type 'boolean'
-261 
-262 :(scenario get_location_indirect)
-263 # 'get-location' can read from container address
-264 def main [
-265   1:num <- copy 10
-266   # 10 reserved for refcount
-267   11:num <- copy 34
-268   12:num <- copy 35
-269   4:location <- get-location 1:&:point/lookup, 0:offset
-270 ]
-271 +mem: storing 11 in location 4
-272 
-273 :(scenario get_location_indirect_2)
-274 def main [
-275   1:num <- copy 10
-276   # 10 reserved for refcount
-277   11:num <- copy 34
-278   12:num <- copy 35
-279   4:&:num <- copy 20/unsafe
-280   4:&:location/lookup <- get-location 1:&:point/lookup, 0:offset
-281 ]
-282 +mem: storing 11 in location 21
-283 
-284 //: allow waiting on a routine to complete
-285 
-286 :(scenario wait_for_routine)
-287 def f1 [
-288   # add a few routines to run
-289   1:num/routine <- start-running f2
-290   2:num/routine <- start-running f3
-291   wait-for-routine 1:num/routine
-292   # now wait for f2 to *complete* and modify location 13 before using its value
-293   20:num <- copy 13:num
-294 ]
-295 def f2 [
-296   10:num <- copy 0  # just padding
-297   switch  # simulate a block; routine f1 shouldn't restart at this point
-298   13:num <- copy 34
-299 ]
-300 def f3 [
-301   # padding routine just to help simulate the block in f2 using 'switch'
-302   11:num <- copy 0
-303   12:num <- copy 0
-304 ]
-305 +schedule: f1
-306 +run: waiting for routine 2
-307 +schedule: f2
-308 +schedule: f3
-309 +schedule: f2
-310 +schedule: waking up routine 1
-311 +schedule: f1
-312 # if we got the synchronization wrong we'd be storing 0 in location 20
-313 +mem: storing 34 in location 20
-314 
-315 :(before "End routine Fields")
-316 // only if state == WAITING
-317 int waiting_on_routine;
-318 :(before "End routine Constructor")
-319 waiting_on_routine = 0;
-320 
-321 :(before "End Primitive Recipe Declarations")
-322 WAIT_FOR_ROUTINE,
-323 :(before "End Primitive Recipe Numbers")
-324 put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE);
-325 :(before "End Primitive Recipe Checks")
-326 case WAIT_FOR_ROUTINE: {
-327   if (SIZE(inst.ingredients) != 1) {
-328   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-329   ¦ break;
-330   }
-331   if (!is_mu_number(inst.ingredients.at(0))) {
-332   ¦ 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();
-333   ¦ break;
-334   }
-335   break;
-336 }
-337 :(before "End Primitive Recipe Implementations")
-338 case WAIT_FOR_ROUTINE: {
-339   if (ingredients.at(0).at(0) == Current_routine->id) {
-340   ¦ raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end();
-341   ¦ break;
-342   }
-343   Current_routine->state = WAITING;
-344   Current_routine->waiting_on_routine = ingredients.at(0).at(0);
-345   trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end();
-346   break;
-347 }
-348 
-349 :(before "End Scheduler State Transitions")
-350 // Wake up any routines waiting for other routines to complete.
-351 // Important: this must come after the scheduler loop above giving routines
-352 // waiting for locations to change a chance to wake up.
-353 for (int i = 0;  i < SIZE(Routines);  ++i) {
-354   if (Routines.at(i)->state != WAITING) continue;
-355   routine* waiter = Routines.at(i);
-356   if (!waiter->waiting_on_routine) continue;
-357   int id = waiter->waiting_on_routine;
-358   assert(id != waiter->id);  // routine can't wait on itself
-359   for (int j = 0;  j < SIZE(Routines);  ++j) {
-360   ¦ const routine* waitee = Routines.at(j);
-361   ¦ if (waitee->id == id && waitee->state != RUNNING && waitee->state != WAITING) {
-362   ¦ ¦ // routine is COMPLETED or DISCONTINUED
-363   ¦ ¦ trace(9999, "schedule") << "waking up routine " << waiter->id << end();
-364   ¦ ¦ waiter->state = RUNNING;
-365   ¦ ¦ waiter->waiting_on_routine = 0;
-366   ¦ }
-367   }
-368 }
-369 
-370 //: yield voluntarily to let some other routine run
-371 
-372 :(before "End Primitive Recipe Declarations")
-373 SWITCH,
-374 :(before "End Primitive Recipe Numbers")
-375 put(Recipe_ordinal, "switch", SWITCH);
-376 :(before "End Primitive Recipe Checks")
-377 case SWITCH: {
-378   break;
-379 }
-380 :(before "End Primitive Recipe Implementations")
-381 case SWITCH: {
-382   ++current_step_index();
-383   goto stop_running_current_routine;
-384 }
-385 
-386 :(scenario switch_preempts_current_routine)
-387 def f1 [
-388   start-running f2
-389   1:num <- copy 34
-390   switch
-391   3:num <- copy 36
-392 ]
-393 def f2 [
-394   2:num <- copy 35
-395 ]
-396 +mem: storing 34 in location 1
-397 # context switch
-398 +mem: storing 35 in location 2
-399 # back to original thread
-400 +mem: storing 36 in location 3
-401 
-402 //:: helpers for manipulating routines in tests
-403 //:
-404 //: Managing arbitrary scenarios requires the ability to:
-405 //:   a) check if a routine is blocked
-406 //:   b) restart a blocked routine ('restart')
-407 //:
-408 //: A routine is blocked either if it's waiting or if it explicitly signals
-409 //: that it's blocked (even as it periodically wakes up and polls for some
-410 //: event).
-411 //:
-412 //: Signalling blockedness might well be a huge hack. But Mu doesn't have Unix
-413 //: signals to avoid polling with, because signals are also pretty hacky.
-414 
-415 :(before "End routine Fields")
-416 bool blocked;
-417 :(before "End routine Constructor")
-418 blocked = false;
-419 
-420 :(before "End Primitive Recipe Declarations")
-421 CURRENT_ROUTINE_IS_BLOCKED,
-422 :(before "End Primitive Recipe Numbers")
-423 put(Recipe_ordinal, "current-routine-is-blocked", CURRENT_ROUTINE_IS_BLOCKED);
-424 :(before "End Primitive Recipe Checks")
-425 case CURRENT_ROUTINE_IS_BLOCKED: {
-426   if (!inst.ingredients.empty()) {
-427   ¦ raise << maybe(get(Recipe, r).name) << "'current-routine-is-blocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end();
-428   ¦ break;
-429   }
-430   break;
-431 }
-432 :(before "End Primitive Recipe Implementations")
-433 case CURRENT_ROUTINE_IS_BLOCKED: {
-434   Current_routine->blocked = true;
-435   break;
-436 }
-437 
-438 :(before "End Primitive Recipe Declarations")
-439 CURRENT_ROUTINE_IS_UNBLOCKED,
-440 :(before "End Primitive Recipe Numbers")
-441 put(Recipe_ordinal, "current-routine-is-unblocked", CURRENT_ROUTINE_IS_UNBLOCKED);
-442 :(before "End Primitive Recipe Checks")
-443 case CURRENT_ROUTINE_IS_UNBLOCKED: {
-444   if (!inst.ingredients.empty()) {
-445   ¦ raise << maybe(get(Recipe, r).name) << "'current-routine-is-unblocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end();
-446   ¦ break;
-447   }
-448   break;
-449 }
-450 :(before "End Primitive Recipe Implementations")
-451 case CURRENT_ROUTINE_IS_UNBLOCKED: {
-452   Current_routine->blocked = false;
-453   break;
-454 }
-455 
-456 //: also allow waiting on a routine to block
-457 //: (just for tests; use wait_for_routine above wherever possible)
-458 
-459 :(scenario wait_for_routine_to_block)
-460 def f1 [
-461   1:num/routine <- start-running f2
-462   wait-for-routine-to-block 1:num/routine
-463   # now wait for f2 to run and modify location 10 before using its value
-464   11:num <- copy 10:num
-465 ]
-466 def f2 [
-467   10:num <- copy 34
-468 ]
-469 +schedule: f1
-470 +run: waiting for routine 2 to block
-471 +schedule: f2
-472 +schedule: waking up routine 1 because routine 2 is blocked
-473 +schedule: f1
-474 # if we got the synchronization wrong we'd be storing 0 in location 11
-475 +mem: storing 34 in location 11
-476 
-477 :(before "End routine Fields")
-478 // only if state == WAITING
-479 int waiting_on_routine_to_block;
-480 :(before "End routine Constructor")
-481 waiting_on_routine_to_block = 0;
-482 
-483 :(before "End Primitive Recipe Declarations")
-484 WAIT_FOR_ROUTINE_TO_BLOCK,
-485 :(before "End Primitive Recipe Numbers")
-486 put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK);
-487 :(before "End Primitive Recipe Checks")
-488 case WAIT_FOR_ROUTINE_TO_BLOCK: {
-489   if (SIZE(inst.ingredients) != 1) {
-490   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-routine-to-block' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-491   ¦ break;
-492   }
-493   if (!is_mu_number(inst.ingredients.at(0))) {
-494   ¦ raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine-to-block' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
-495   ¦ break;
-496   }
-497   break;
-498 }
-499 :(before "End Primitive Recipe Implementations")
-500 case WAIT_FOR_ROUTINE_TO_BLOCK: {
-501   if (ingredients.at(0).at(0) == Current_routine->id) {
-502   ¦ raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end();
-503   ¦ break;
-504   }
-505   Current_routine->state = WAITING;
-506   Current_routine->waiting_on_routine_to_block = ingredients.at(0).at(0);
-507   trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << " to block" << end();
-508   break;
-509 }
-510 
-511 :(before "End Scheduler State Transitions")
-512 // Wake up any routines waiting for other routines to stop running.
-513 for (int i = 0;  i < SIZE(Routines);  ++i) {
-514   if (Routines.at(i)->state != WAITING) continue;
-515   routine* waiter = Routines.at(i);
-516   if (!waiter->waiting_on_routine_to_block) continue;
-517   int id = waiter->waiting_on_routine_to_block;
-518   assert(id != waiter->id);  // routine can't wait on itself
-519   for (int j = 0;  j < SIZE(Routines);  ++j) {
-520   ¦ const routine* waitee = Routines.at(j);
-521   ¦ if (waitee->id != id) continue;
-522   ¦ if (waitee->state != RUNNING || waitee->blocked) {
-523   ¦ ¦ trace(9999, "schedule") << "waking up routine " << waiter->id << " because routine " << waitee->id << " is blocked" << end();
-524   ¦ ¦ waiter->state = RUNNING;
-525   ¦ ¦ waiter->waiting_on_routine_to_block = 0;
-526   ¦ }
-527   }
-528 }
-529 
-530 //: helper for restarting blocking routines in tests
-531 
-532 :(before "End Primitive Recipe Declarations")
-533 RESTART,
-534 :(before "End Primitive Recipe Numbers")
-535 put(Recipe_ordinal, "restart", RESTART);
-536 :(before "End Primitive Recipe Checks")
-537 case RESTART: {
-538   if (SIZE(inst.ingredients) != 1) {
-539   ¦ raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
-540   ¦ break;
-541   }
-542   if (!is_mu_number(inst.ingredients.at(0))) {
-543   ¦ 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();
-544   ¦ break;
-545   }
-546   break;
-547 }
-548 :(before "End Primitive Recipe Implementations")
-549 case RESTART: {
-550   int id = ingredients.at(0).at(0);
-551   for (int i = 0;  i < SIZE(Routines);  ++i) {
-552   ¦ if (Routines.at(i)->id == id) {
-553   ¦ ¦ if (Routines.at(i)->state == WAITING)
-554   ¦ ¦ ¦ Routines.at(i)->state = RUNNING;
-555   ¦ ¦ Routines.at(i)->blocked = false;
-556   ¦ ¦ break;
-557   ¦ }
-558   }
-559   break;
-560 }
-561 
-562 :(scenario cannot_restart_completed_routine)
-563 % Scheduling_interval = 1;
-564 def main [
-565   local-scope
-566   r:num/routine-id <- start-running f
-567   x:num <- copy 0  # wait for f to be scheduled
-568   # r is COMPLETED by this point
-569   restart r  # should have no effect
-570   x:num <- copy 0  # give f time to be scheduled (though it shouldn't be)
-571 ]
-572 def f [
-573   1:num/raw <- copy 1
-574 ]
-575 # shouldn't crash
-576 
-577 :(scenario restart_blocked_routine)
-578 % Scheduling_interval = 1;
-579 def main [
-580   local-scope
-581   r:num/routine-id <- start-running f
-582   wait-for-routine-to-block r  # get past the block in f below
-583   restart r
-584   wait-for-routine-to-block r  # should run f to completion
-585 ]
-586 # function with one block
-587 def f [
-588   current-routine-is-blocked
-589   # 8 instructions of padding, many more than 'main' above
-590   1:num <- add 1:num, 1
-591   1:num <- add 1:num, 1
-592   1:num <- add 1:num, 1
-593   1:num <- add 1:num, 1
-594   1:num <- add 1:num, 1
-595   1:num <- add 1:num, 1
-596   1:num <- add 1:num, 1
-597   1:num <- add 1:num, 1
-598   1:num <- add 1:num, 1
-599 ]
-600 # make sure all of f ran
-601 +mem: storing 8 in location 1
-
- - - diff --git a/html/074deep_copy.cc.html b/html/074deep_copy.cc.html deleted file mode 100644 index 6fde668c..00000000 --- a/html/074deep_copy.cc.html +++ /dev/null @@ -1,458 +0,0 @@ - - - - -Mu - 074deep_copy.cc - - - - - - - - - - -
-  1 // To recursively copy containers and any addresses they contain, use
-  2 // 'deep-copy'.
-  3 //
-  4 // Invariant: After a deep-copy its ingredient and result will point to no
-  5 // common addresses.
-  6 // Implications: Refcounts of all data pointed to by the original ingredient
-  7 // will remain unchanged. Refcounts of all data pointed to by the (newly
-  8 // created) result will be 1, in the absence of cycles.
-  9 //
- 10 // We do handle cycles in the ingredient, however. All cycles are translated
- 11 // to new cycles in the product.
- 12 
- 13 :(scenario deep_copy_number)
- 14 def main [
- 15   local-scope
- 16   x:num <- copy 34
- 17   y:num <- deep-copy x
- 18   10:bool/raw <- equal x, y
- 19 ]
- 20 # non-address primitives are identical
- 21 +mem: storing 1 in location 10
- 22 
- 23 :(scenario deep_copy_container_without_address)
- 24 container foo [
- 25   x:num
- 26   y:num
- 27 ]
- 28 def main [
- 29   local-scope
- 30   a:foo <- merge 34, 35
- 31   b:foo <- deep-copy a
- 32   10:bool/raw <- equal a, b
- 33 ]
- 34 # containers are identical as long as they don't contain addresses
- 35 +mem: storing 1 in location 10
- 36 
- 37 :(scenario deep_copy_address)
- 38 % Memory_allocated_until = 200;
- 39 def main [
- 40   # avoid all memory allocations except the implicit ones inside deep-copy, so
- 41   # that the result is deterministic
- 42   1:&:num <- copy 100/unsafe  # pretend allocation
- 43   *1:&:num <- copy 34
- 44   2:&:num <- deep-copy 1:&:num
- 45   10:bool <- equal 1:&:num, 2:&:num
- 46   11:bool <- equal *1:&:num, *2:&:num
- 47   2:&:num <- copy 0
- 48 ]
- 49 # the result of deep-copy is a new address
- 50 +mem: storing 0 in location 10
- 51 # however, the contents are identical
- 52 +mem: storing 1 in location 11
- 53 # the result of deep-copy gets a refcount of 1
- 54 # (its address 202 = 200 base + 2 for temporary space inside deep-copy)
- 55 +run: {2: ("address" "number")} <- copy {0: "literal"}
- 56 +mem: decrementing refcount of 202: 1 -> 0
- 57 +abandon: saving 202 in free-list of size 2
- 58 
- 59 :(scenario deep_copy_address_to_container)
- 60 % Memory_allocated_until = 200;
- 61 def main [
- 62   # avoid all memory allocations except the implicit ones inside deep-copy, so
- 63   # that the result is deterministic
- 64   1:&:point <- copy 100/unsafe  # pretend allocation
- 65   *1:&:point <- merge 34, 35
- 66   2:&:point <- deep-copy 1:&:point
- 67   10:bool <- equal 1:&:point, 2:&:point
- 68   11:bool <- equal *1:&:point, *2:&:point
- 69 ]
- 70 # the result of deep-copy is a new address
- 71 +mem: storing 0 in location 10
- 72 # however, the contents are identical
- 73 +mem: storing 1 in location 11
- 74 
- 75 :(scenario deep_copy_address_to_address)
- 76 % Memory_allocated_until = 200;
- 77 def main [
- 78   # avoid all memory allocations except the implicit ones inside deep-copy, so
- 79   # that the result is deterministic
- 80   1:&:&:num <- copy 100/unsafe  # pretend allocation
- 81   *1:&:&:num <- copy 150/unsafe
- 82   **1:&:&:num <- copy 34
- 83   2:&:&:num <- deep-copy 1:&:&:num
- 84   10:bool <- equal 1:&:&:num, 2:&:&:num
- 85   11:bool <- equal *1:&:&:num, *2:&:&:num
- 86   12:bool <- equal **1:&:&:num, **2:&:&:num
- 87 ]
- 88 # the result of deep-copy is a new address
- 89 +mem: storing 0 in location 10
- 90 # any addresses in it or pointed to it are also new
- 91 +mem: storing 0 in location 11
- 92 # however, the non-address contents are identical
- 93 +mem: storing 1 in location 12
- 94 
- 95 :(scenario deep_copy_array)
- 96 % Memory_allocated_until = 200;
- 97 def main [
- 98   # avoid all memory allocations except the implicit ones inside deep-copy, so
- 99   # that the result is deterministic
-100   100:num <- copy 1  # pretend refcount
-101   101:num <- copy 3  # pretend array length
-102   1:&:@:num <- copy 100/unsafe  # pretend allocation
-103   put-index *1:&:@:num, 0, 34
-104   put-index *1:&:@:num, 1, 35
-105   put-index *1:&:@:num, 2, 36
-106   stash [old:], *1:&:@:num
-107   2:&:@:num <- deep-copy 1:&:@:num
-108   stash 2:&:@:num
-109   stash [new:], *2:&:@:num
-110   10:bool <- equal 1:&:@:num, 2:&:@:num
-111   11:bool <- equal *1:&:@:num, *2:&:@:num
-112 ]
-113 +app: old: 3 34 35 36
-114 +app: new: 3 34 35 36
-115 # the result of deep-copy is a new address
-116 +mem: storing 0 in location 10
-117 # however, the contents are identical
-118 +mem: storing 1 in location 11
-119 
-120 :(scenario deep_copy_container_with_address)
-121 container foo [
-122   x:num
-123   y:&:num
-124 ]
-125 def main [
-126   local-scope
-127   y0:&:num <- new number:type
-128   *y0 <- copy 35
-129   a:foo <- merge 34, y0
-130   b:foo <- deep-copy a
-131   10:bool/raw <- equal a, b
-132   y1:&:num <- get b, y:offset
-133   11:bool/raw <- equal y0, y1
-134   12:num/raw <- copy *y1
-135 ]
-136 # containers containing addresses are not identical to their deep copies
-137 +mem: storing 0 in location 10
-138 # the addresses they contain are not identical either
-139 +mem: storing 0 in location 11
-140 +mem: storing 35 in location 12
-141 
-142 :(scenario deep_copy_exclusive_container_with_address)
-143 exclusive-container foo [
-144   x:num
-145   y:&:num
-146 ]
-147 def main [
-148   local-scope
-149   y0:&:num <- new number:type
-150   *y0 <- copy 34
-151   a:foo <- merge 1/y, y0
-152   b:foo <- deep-copy a
-153   10:bool/raw <- equal a, b
-154   y1:&:num, z:bool <- maybe-convert b, y:variant
-155   11:bool/raw <- equal y0, y1
-156   12:num/raw <- copy *y1
-157 ]
-158 # exclusive containers containing addresses are not identical to their deep copies
-159 +mem: storing 0 in location 10
-160 # the addresses they contain are not identical either
-161 +mem: storing 0 in location 11
-162 +mem: storing 34 in location 12
-163 
-164 :(scenario deep_copy_exclusive_container_with_container_with_address)
-165 exclusive-container foo [
-166   x:num
-167   y:bar  # inline
-168 ]
-169 container bar [
-170   x:&:num
-171 ]
-172 def main [
-173   local-scope
-174   y0:&:num <- new number:type
-175   *y0 <- copy 34
-176   a:bar <- merge y0
-177   b:foo <- merge 1/y, a
-178   c:foo <- deep-copy b
-179   10:bool/raw <- equal b, c
-180   d:bar, z:bool <- maybe-convert c, y:variant
-181   y1:&:num <- get d, x:offset
-182   11:bool/raw <- equal y0, y1
-183   12:num/raw <- copy *y1
-184 ]
-185 # exclusive containers containing addresses are not identical to their deep copies
-186 +mem: storing 0 in location 10
-187 # sub-containers containing addresses are not identical either
-188 +mem: storing 0 in location 11
-189 +mem: storing 34 in location 12
-190 
-191 :(before "End Primitive Recipe Declarations")
-192 DEEP_COPY,
-193 :(before "End Primitive Recipe Numbers")
-194 put(Recipe_ordinal, "deep-copy", DEEP_COPY);
-195 :(before "End Primitive Recipe Checks")
-196 case DEEP_COPY: {
-197   if (SIZE(inst.ingredients) != 1) {
-198   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
-199   ¦ break;
-200   }
-201   if (SIZE(inst.products) != 1) {
-202   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
-203   ¦ break;
-204   }
-205   if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) {
-206   ¦ raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << to_original_string(inst) << "'\n" << end();
-207   ¦ break;
-208   }
-209   break;
-210 }
-211 :(before "End Primitive Recipe Implementations")
-212 case DEEP_COPY: {
-213   const reagent& input = current_instruction().ingredients.at(0);
-214   // allocate a tiny bit of temporary space for deep_copy()
-215   trace(9991, "run") << "deep-copy: allocating space for temporary" << end();
-216   reagent tmp("tmp:address:number");
-217   tmp.set_value(allocate(1));
-218   products.push_back(deep_copy(input, tmp));
-219   // reclaim Mu memory allocated for tmp
-220   trace(9991, "run") << "deep-copy: reclaiming temporary" << end();
-221   abandon(tmp.value, payload_type(tmp.type), payload_size(tmp));
-222   // reclaim host memory allocated for tmp.type when tmp goes out of scope
-223   break;
-224 }
-225 
-226 :(code)
-227 vector<double> deep_copy(const reagent& in, const reagent& tmp) {
-228   map<int, int> addresses_copied;
-229   return deep_copy(in, addresses_copied, tmp);
-230 }
-231 
-232 vector<double> deep_copy(reagent/*copy*/ in, map<int, int>& addresses_copied, const reagent& tmp) {
-233   canonize(in);
-234   vector<double> result;
-235   if (is_mu_address(in))
-236   ¦ result.push_back(deep_copy_address(in, addresses_copied, tmp));
-237   else
-238   ¦ deep_copy(in, addresses_copied, tmp, result);
-239   return result;
-240 }
-241 
-242 // deep-copy an address and return a new address
-243 int deep_copy_address(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp) {
-244   if (canonized_in.value == 0) return 0;
-245   int in_address = payload_address(canonized_in);
-246   trace(9991, "run") << "deep-copy: copying address " << in_address << end();
-247   if (contains_key(addresses_copied, in_address)) {
-248   ¦ int out = get(addresses_copied, in_address);
-249   ¦ trace(9991, "run") << "deep-copy: copy already exists: " << out << end();
-250   ¦ return out;
-251   }
-252   int out = allocate(payload_size(canonized_in));
-253   trace(9991, "run") << "deep-copy: new address is " << out << end();
-254   put(addresses_copied, in_address, out);
-255   reagent/*copy*/ payload = canonized_in;
-256   payload.properties.push_back(pair<string, string_tree*>("lookup", NULL));
-257   trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end();
-258   vector<double> data = deep_copy(payload, addresses_copied, tmp);
-259   trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end();
-260   // HACK: write_memory interface isn't ideal for this situation; we need
-261   // a temporary location to help copy the payload.
-262   trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end();
-263   put(Memory, tmp.value, out);
-264   payload.set_value(tmp.value);  // now modified for output
-265   vector<double> old_data = read_memory(payload);
-266   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();
-267   write_memory(payload, data);
-268   trace(9991, "run") << "deep-copy: output is " << to_string(data) << end();
-269   return out;
-270 }
-271 
-272 // deep-copy a non-address and return a vector of locations
-273 void deep_copy(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp, vector<double>& out) {
-274   assert(!is_mu_address(canonized_in));
-275   vector<double> data = read_memory(canonized_in);
-276   out.insert(out.end(), data.begin(), data.end());
-277   if (!contains_key(Container_metadata, canonized_in.type)) return;
-278   trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end();
-279   const container_metadata& metadata = get(Container_metadata, canonized_in.type);
-280   for (map<set<tag_condition_info>, set<address_element_info> >::const_iterator p = metadata.address.begin();  p != metadata.address.end();  ++p) {
-281   ¦ if (!all_match(data, p->first)) continue;
-282   ¦ for (set<address_element_info>::const_iterator info = p->second.begin();  info != p->second.end();  ++info) {
-283   ¦ ¦ // construct a fake reagent that reads directly from the appropriate
-284   ¦ ¦ // field of the container
-285   ¦ ¦ reagent curr;
-286   ¦ ¦ if (info->payload_type->atom)
-287   ¦ ¦ ¦ curr.type = new type_tree(new type_tree("address"), new type_tree(new type_tree(info->payload_type->name), NULL));
-288   ¦ ¦ else
-289   ¦ ¦ ¦ curr.type = new type_tree(new type_tree("address"), new type_tree(*info->payload_type));
-290   ¦ ¦ curr.set_value(canonized_in.value + info->offset);
-291   ¦ ¦ curr.properties.push_back(pair<string, string_tree*>("raw", NULL));
-292   ¦ ¦ trace(9991, "run") << "deep-copy: copying address " << curr.value << end();
-293   ¦ ¦ out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp);
-294   ¦ }
-295   }
-296 }
-297 
-298 int payload_address(reagent/*copy*/ x) {
-299   x.properties.push_back(pair<string, string_tree*>("lookup", NULL));
-300   canonize(x);
-301   return x.value;
-302 }
-303 
-304 //: moar tests, just because I can't believe it all works
-305 
-306 :(scenario deep_copy_stress_test_1)
-307 container foo1 [
-308   p:&:num
-309 ]
-310 container foo2 [
-311   p:&:foo1
-312 ]
-313 exclusive-container foo3 [
-314   p:&:foo1
-315   q:&:foo2
-316 ]
-317 def main [
-318   local-scope
-319   x:&:num <- new number:type
-320   *x <- copy 34
-321   a:&:foo1 <- new foo1:type
-322   *a <- merge x
-323   b:&:foo2 <- new foo2:type
-324   *b <- merge a
-325   c:foo3 <- merge 1/q, b
-326   d:foo3 <- deep-copy c
-327   e:&:foo2, z:bool <- maybe-convert d, q:variant
-328   f:&:foo1 <- get *e, p:offset
-329   g:&:num <- get *f, p:offset
-330   1:num/raw <- copy *g
-331 ]
-332 +mem: storing 34 in location 1
-333 
-334 :(scenario deep_copy_stress_test_2)
-335 container foo1 [
-336   p:&:num
-337 ]
-338 container foo2 [
-339   p:&:foo1
-340 ]
-341 exclusive-container foo3 [
-342   p:&:foo1
-343   q:&:foo2
-344 ]
-345 container foo4 [
-346   p:num
-347   q:&:foo3
-348 ]
-349 def main [
-350   local-scope
-351   x:&:num <- new number:type
-352   *x <- copy 34
-353   a:&:foo1 <- new foo1:type
-354   *a <- merge x
-355   b:&:foo2 <- new foo2:type
-356   *b <- merge a
-357   c:&:foo3 <- new foo3:type
-358   *c <- merge 1/q, b
-359   d:foo4 <- merge 35, c
-360   e:foo4 <- deep-copy d
-361   f:&:foo3 <- get e, q:offset
-362   g:&:foo2, z:bool <- maybe-convert *f, q:variant
-363   h:&:foo1 <- get *g, p:offset
-364   y:&:num <- get *h, p:offset
-365   1:num/raw <- copy *y
-366 ]
-367 +mem: storing 34 in location 1
-368 
-369 :(scenario deep_copy_cycles)
-370 container foo [
-371   p:num
-372   q:&:foo
-373 ]
-374 def main [
-375   local-scope
-376   x:&:foo <- new foo:type
-377   *x <- put *x, p:offset, 34
-378   *x <- put *x, q:offset, x  # create a cycle
-379   y:&:foo <- deep-copy x
-380   1:num/raw <- get *y, p:offset
-381   y2:&:foo <- get *y, q:offset
-382   stash y [vs] y2
-383   2:bool/raw <- equal y, y2  # is it still a cycle?
-384   3:bool/raw <- equal x, y  # is it the same cycle?
-385 ]
-386 +mem: storing 34 in location 1
-387 # deep copy also contains a cycle
-388 +mem: storing 1 in location 2
-389 # but it's a completely different (disjoint) cycle
-390 +mem: storing 0 in location 3
-
- - - diff --git a/html/074wait.cc.html b/html/074wait.cc.html new file mode 100644 index 00000000..eee7a236 --- /dev/null +++ b/html/074wait.cc.html @@ -0,0 +1,670 @@ + + + + +Mu - 074wait.cc + + + + + + + + + + +
+  1 //: Routines can be put in a 'waiting' state, from which it will be ready to
+  2 //: run again when a specific memory location changes its value. This is Mu's
+  3 //: basic technique for orchestrating the order in which different routines
+  4 //: operate.
+  5 
+  6 :(scenario wait_for_location)
+  7 def f1 [
+  8   10:num <- copy 34
+  9   start-running f2
+ 10   20:location <- copy 10/unsafe
+ 11   wait-for-reset-then-set 20:location
+ 12   # wait for f2 to run and reset location 1
+ 13   30:num <- copy 10:num
+ 14 ]
+ 15 def f2 [
+ 16   10:location <- copy 0/unsafe
+ 17 ]
+ 18 +schedule: f1
+ 19 +run: waiting for location 10 to reset
+ 20 +schedule: f2
+ 21 +schedule: waking up routine 1
+ 22 +schedule: f1
+ 23 +mem: storing 1 in location 30
+ 24 
+ 25 //: define the new state that all routines can be in
+ 26 
+ 27 :(before "End routine States")
+ 28 WAITING,
+ 29 :(before "End routine Fields")
+ 30 // only if state == WAITING
+ 31 int waiting_on_location;
+ 32 :(before "End routine Constructor")
+ 33 waiting_on_location = 0;
+ 34 
+ 35 :(before "End Mu Test Teardown")
+ 36 if (Passed && any_routines_waiting())
+ 37   raise << Current_scenario->name << ": deadlock!\n" << end();
+ 38 :(before "End Run Routine")
+ 39 if (any_routines_waiting()) {
+ 40   raise << "deadlock!\n" << end();
+ 41   dump_waiting_routines();
+ 42 }
+ 43 :(before "End Test Teardown")
+ 44 if (Passed && any_routines_with_error())
+ 45   raise << "some routines died with errors\n" << end();
+ 46 :(code)
+ 47 bool any_routines_waiting() {
+ 48   for (int i = 0;  i < SIZE(Routines);  ++i) {
+ 49   ¦ if (Routines.at(i)->state == WAITING)
+ 50   ¦ ¦ return true;
+ 51   }
+ 52   return false;
+ 53 }
+ 54 void dump_waiting_routines() {
+ 55   for (int i = 0;  i < SIZE(Routines);  ++i) {
+ 56   ¦ if (Routines.at(i)->state == WAITING)
+ 57   ¦ ¦ cerr << i << ": " << routine_label(Routines.at(i)) << '\n';
+ 58   }
+ 59 }
+ 60 
+ 61 :(scenario wait_for_location_can_deadlock)
+ 62 % Hide_errors = true;
+ 63 def main [
+ 64   10:num <- copy 1
+ 65   20:location <- copy 10/unsafe
+ 66   wait-for-reset-then-set 20:location
+ 67 ]
+ 68 +error: deadlock!
+ 69 
+ 70 //: Primitive recipe to put routines in that state.
+ 71 //: This primitive is also known elsewhere as compare-and-set (CAS). Used to
+ 72 //: build locks.
+ 73 
+ 74 :(before "End Primitive Recipe Declarations")
+ 75 WAIT_FOR_RESET_THEN_SET,
+ 76 :(before "End Primitive Recipe Numbers")
+ 77 put(Recipe_ordinal, "wait-for-reset-then-set", WAIT_FOR_RESET_THEN_SET);
+ 78 :(before "End Primitive Recipe Checks")
+ 79 case WAIT_FOR_RESET_THEN_SET: {
+ 80   if (SIZE(inst.ingredients) != 1) {
+ 81   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+ 82   ¦ break;
+ 83   }
+ 84   if (!is_mu_location(inst.ingredients.at(0))) {
+ 85   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
+ 86   }
+ 87   break;
+ 88 }
+ 89 :(before "End Primitive Recipe Implementations")
+ 90 case WAIT_FOR_RESET_THEN_SET: {
+ 91   int loc = static_cast<int>(ingredients.at(0).at(0));
+ 92   trace(9998, "run") << "wait: *" << loc << " = " << get_or_insert(Memory, loc) << end();
+ 93   if (get_or_insert(Memory, loc) == 0) {
+ 94   ¦ trace(9998, "run") << "location " << loc << " is already 0; setting" << end();
+ 95   ¦ put(Memory, loc, 1);
+ 96   ¦ break;
+ 97   }
+ 98   trace(9998, "run") << "waiting for location " << loc << " to reset" << end();
+ 99   Current_routine->state = WAITING;
+100   Current_routine->waiting_on_location = loc;
+101   break;
+102 }
+103 
+104 //: Counterpart to unlock a lock.
+105 :(before "End Primitive Recipe Declarations")
+106 RESET,
+107 :(before "End Primitive Recipe Numbers")
+108 put(Recipe_ordinal, "reset", RESET);
+109 :(before "End Primitive Recipe Checks")
+110 case RESET: {
+111   if (SIZE(inst.ingredients) != 1) {
+112   ¦ raise << maybe(get(Recipe, r).name) << "'reset' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+113   ¦ break;
+114   }
+115   if (!is_mu_location(inst.ingredients.at(0))) {
+116   ¦ raise << maybe(get(Recipe, r).name) << "'reset' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
+117   }
+118   break;
+119 }
+120 :(before "End Primitive Recipe Implementations")
+121 case RESET: {
+122   int loc = static_cast<int>(ingredients.at(0).at(0));
+123   put(Memory, loc, 0);
+124   trace(9998, "run") << "reset: *" << loc << " = " << get_or_insert(Memory, loc) << end();
+125   break;
+126 }
+127 
+128 //: scheduler tweak to get routines out of that state
+129 
+130 :(before "End Scheduler State Transitions")
+131 for (int i = 0;  i < SIZE(Routines);  ++i) {
+132   if (Routines.at(i)->state != WAITING) continue;
+133   int loc = Routines.at(i)->waiting_on_location;
+134   if (loc && get_or_insert(Memory, loc) == 0) {
+135   ¦ trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end();
+136   ¦ put(Memory, loc, 1);
+137   ¦ Routines.at(i)->state = RUNNING;
+138   ¦ Routines.at(i)->waiting_on_location = 0;
+139   }
+140 }
+141 
+142 //: Primitive to help compute locations to wait on.
+143 //: Only supports elements immediately inside containers; no arrays or
+144 //: containers within containers yet.
+145 
+146 :(scenario get_location)
+147 def main [
+148   12:num <- copy 34
+149   13:num <- copy 35
+150   15:location <- get-location 12:point, 1:offset
+151 ]
+152 +mem: storing 13 in location 15
+153 
+154 :(before "End Primitive Recipe Declarations")
+155 GET_LOCATION,
+156 :(before "End Primitive Recipe Numbers")
+157 put(Recipe_ordinal, "get-location", GET_LOCATION);
+158 :(before "End Primitive Recipe Checks")
+159 case GET_LOCATION: {
+160   if (SIZE(inst.ingredients) != 2) {
+161   ¦ raise << maybe(get(Recipe, r).name) << "'get-location' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end();
+162   ¦ break;
+163   }
+164   reagent/*copy*/ base = inst.ingredients.at(0);
+165   if (!canonize_type(base)) break;
+166   if (!base.type) {
+167   ¦ 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();
+168   ¦ break;
+169   }
+170   const type_tree* base_root_type = base.type->atom ? base.type : base.type->left;
+171   if (!base_root_type->atom || base_root_type->value == 0 || !contains_key(Type, base_root_type->value) || get(Type, base_root_type->value).kind != CONTAINER) {
+172   ¦ 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();
+173   ¦ break;
+174   }
+175   type_ordinal base_type = base.type->value;
+176   const reagent& offset = inst.ingredients.at(1);
+177   if (!is_literal(offset) || !is_mu_scalar(offset)) {
+178   ¦ 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();
+179   ¦ break;
+180   }
+181   int offset_value = 0;
+182   //: later layers will permit non-integer offsets
+183   if (is_integer(offset.name)) {
+184   ¦ offset_value = to_integer(offset.name);
+185   ¦ if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) {
+186   ¦ ¦ raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for '" << get(Type, base_type).name << "'\n" << end();
+187   ¦ ¦ break;
+188   ¦ }
+189   }
+190   else {
+191   ¦ offset_value = offset.value;
+192   }
+193   if (inst.products.empty()) break;
+194   if (!is_mu_location(inst.products.at(0))) {
+195   ¦ 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();
+196   ¦ break;
+197   }
+198   break;
+199 }
+200 :(before "End Primitive Recipe Implementations")
+201 case GET_LOCATION: {
+202   reagent/*copy*/ base = current_instruction().ingredients.at(0);
+203   canonize(base);
+204   int base_address = base.value;
+205   if (base_address == 0) {
+206   ¦ raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end();
+207   ¦ break;
+208   }
+209   const type_tree* base_type = get_base_type(base.type);
+210   int offset = ingredients.at(1).at(0);
+211   if (offset < 0 || offset >= SIZE(get(Type, base_type->value).elements)) break;  // copied from Check above
+212   int result = base_address;
+213   for (int i = 0;  i < offset;  ++i)
+214   ¦ result += size_of(element_type(base.type, i));
+215   trace(9998, "run") << "address to copy is " << result << end();
+216   products.resize(1);
+217   products.at(0).push_back(result);
+218   break;
+219 }
+220 
+221 :(code)
+222 bool is_mu_location(reagent/*copy*/ x) {
+223   if (!canonize_type(x)) return false;
+224   if (!x.type) return false;
+225   if (!x.type->atom) return false;
+226   return x.type->value == get(Type_ordinal, "location");
+227 }
+228 
+229 :(scenario get_location_out_of_bounds)
+230 % Hide_errors = true;
+231 def main [
+232   12:num <- copy 34
+233   13:num <- copy 35
+234   14:num <- copy 36
+235   get-location 12:point-number/raw, 2:offset  # point-number occupies 3 locations but has only 2 fields; out of bounds
+236 ]
+237 +error: main: invalid offset 2 for 'point-number'
+238 
+239 :(scenario get_location_out_of_bounds_2)
+240 % Hide_errors = true;
+241 def main [
+242   12:num <- copy 34
+243   13:num <- copy 35
+244   14:num <- copy 36
+245   get-location 12:point-number/raw, -1:offset
+246 ]
+247 +error: main: invalid offset -1 for 'point-number'
+248 
+249 :(scenario get_location_product_type_mismatch)
+250 % Hide_errors = true;
+251 container boolbool [
+252   x:bool
+253   y:bool
+254 ]
+255 def main [
+256   12:bool <- copy 1
+257   13:bool <- copy 0
+258   15:bool <- get-location 12:boolbool, 1:offset
+259 ]
+260 +error: main: 'get-location 12:boolbool, 1:offset' should write to type location but '15' has type 'boolean'
+261 
+262 :(scenario get_location_indirect)
+263 # 'get-location' can read from container address
+264 def main [
+265   1:num <- copy 10
+266   # 10 reserved for refcount
+267   11:num <- copy 34
+268   12:num <- copy 35
+269   4:location <- get-location 1:&:point/lookup, 0:offset
+270 ]
+271 +mem: storing 11 in location 4
+272 
+273 :(scenario get_location_indirect_2)
+274 def main [
+275   1:num <- copy 10
+276   # 10 reserved for refcount
+277   11:num <- copy 34
+278   12:num <- copy 35
+279   4:&:num <- copy 20/unsafe
+280   4:&:location/lookup <- get-location 1:&:point/lookup, 0:offset
+281 ]
+282 +mem: storing 11 in location 21
+283 
+284 //: allow waiting on a routine to complete
+285 
+286 :(scenario wait_for_routine)
+287 def f1 [
+288   # add a few routines to run
+289   1:num/routine <- start-running f2
+290   2:num/routine <- start-running f3
+291   wait-for-routine 1:num/routine
+292   # now wait for f2 to *complete* and modify location 13 before using its value
+293   20:num <- copy 13:num
+294 ]
+295 def f2 [
+296   10:num <- copy 0  # just padding
+297   switch  # simulate a block; routine f1 shouldn't restart at this point
+298   13:num <- copy 34
+299 ]
+300 def f3 [
+301   # padding routine just to help simulate the block in f2 using 'switch'
+302   11:num <- copy 0
+303   12:num <- copy 0
+304 ]
+305 +schedule: f1
+306 +run: waiting for routine 2
+307 +schedule: f2
+308 +schedule: f3
+309 +schedule: f2
+310 +schedule: waking up routine 1
+311 +schedule: f1
+312 # if we got the synchronization wrong we'd be storing 0 in location 20
+313 +mem: storing 34 in location 20
+314 
+315 :(before "End routine Fields")
+316 // only if state == WAITING
+317 int waiting_on_routine;
+318 :(before "End routine Constructor")
+319 waiting_on_routine = 0;
+320 
+321 :(before "End Primitive Recipe Declarations")
+322 WAIT_FOR_ROUTINE,
+323 :(before "End Primitive Recipe Numbers")
+324 put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE);
+325 :(before "End Primitive Recipe Checks")
+326 case WAIT_FOR_ROUTINE: {
+327   if (SIZE(inst.ingredients) != 1) {
+328   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+329   ¦ break;
+330   }
+331   if (!is_mu_number(inst.ingredients.at(0))) {
+332   ¦ 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();
+333   ¦ break;
+334   }
+335   break;
+336 }
+337 :(before "End Primitive Recipe Implementations")
+338 case WAIT_FOR_ROUTINE: {
+339   if (ingredients.at(0).at(0) == Current_routine->id) {
+340   ¦ raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end();
+341   ¦ break;
+342   }
+343   Current_routine->state = WAITING;
+344   Current_routine->waiting_on_routine = ingredients.at(0).at(0);
+345   trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end();
+346   break;
+347 }
+348 
+349 :(before "End Scheduler State Transitions")
+350 // Wake up any routines waiting for other routines to complete.
+351 // Important: this must come after the scheduler loop above giving routines
+352 // waiting for locations to change a chance to wake up.
+353 for (int i = 0;  i < SIZE(Routines);  ++i) {
+354   if (Routines.at(i)->state != WAITING) continue;
+355   routine* waiter = Routines.at(i);
+356   if (!waiter->waiting_on_routine) continue;
+357   int id = waiter->waiting_on_routine;
+358   assert(id != waiter->id);  // routine can't wait on itself
+359   for (int j = 0;  j < SIZE(Routines);  ++j) {
+360   ¦ const routine* waitee = Routines.at(j);
+361   ¦ if (waitee->id == id && waitee->state != RUNNING && waitee->state != WAITING) {
+362   ¦ ¦ // routine is COMPLETED or DISCONTINUED
+363   ¦ ¦ trace(9999, "schedule") << "waking up routine " << waiter->id << end();
+364   ¦ ¦ waiter->state = RUNNING;
+365   ¦ ¦ waiter->waiting_on_routine = 0;
+366   ¦ }
+367   }
+368 }
+369 
+370 //: yield voluntarily to let some other routine run
+371 
+372 :(before "End Primitive Recipe Declarations")
+373 SWITCH,
+374 :(before "End Primitive Recipe Numbers")
+375 put(Recipe_ordinal, "switch", SWITCH);
+376 :(before "End Primitive Recipe Checks")
+377 case SWITCH: {
+378   break;
+379 }
+380 :(before "End Primitive Recipe Implementations")
+381 case SWITCH: {
+382   ++current_step_index();
+383   goto stop_running_current_routine;
+384 }
+385 
+386 :(scenario switch_preempts_current_routine)
+387 def f1 [
+388   start-running f2
+389   1:num <- copy 34
+390   switch
+391   3:num <- copy 36
+392 ]
+393 def f2 [
+394   2:num <- copy 35
+395 ]
+396 +mem: storing 34 in location 1
+397 # context switch
+398 +mem: storing 35 in location 2
+399 # back to original thread
+400 +mem: storing 36 in location 3
+401 
+402 //:: helpers for manipulating routines in tests
+403 //:
+404 //: Managing arbitrary scenarios requires the ability to:
+405 //:   a) check if a routine is blocked
+406 //:   b) restart a blocked routine ('restart')
+407 //:
+408 //: A routine is blocked either if it's waiting or if it explicitly signals
+409 //: that it's blocked (even as it periodically wakes up and polls for some
+410 //: event).
+411 //:
+412 //: Signalling blockedness might well be a huge hack. But Mu doesn't have Unix
+413 //: signals to avoid polling with, because signals are also pretty hacky.
+414 
+415 :(before "End routine Fields")
+416 bool blocked;
+417 :(before "End routine Constructor")
+418 blocked = false;
+419 
+420 :(before "End Primitive Recipe Declarations")
+421 CURRENT_ROUTINE_IS_BLOCKED,
+422 :(before "End Primitive Recipe Numbers")
+423 put(Recipe_ordinal, "current-routine-is-blocked", CURRENT_ROUTINE_IS_BLOCKED);
+424 :(before "End Primitive Recipe Checks")
+425 case CURRENT_ROUTINE_IS_BLOCKED: {
+426   if (!inst.ingredients.empty()) {
+427   ¦ raise << maybe(get(Recipe, r).name) << "'current-routine-is-blocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end();
+428   ¦ break;
+429   }
+430   break;
+431 }
+432 :(before "End Primitive Recipe Implementations")
+433 case CURRENT_ROUTINE_IS_BLOCKED: {
+434   Current_routine->blocked = true;
+435   break;
+436 }
+437 
+438 :(before "End Primitive Recipe Declarations")
+439 CURRENT_ROUTINE_IS_UNBLOCKED,
+440 :(before "End Primitive Recipe Numbers")
+441 put(Recipe_ordinal, "current-routine-is-unblocked", CURRENT_ROUTINE_IS_UNBLOCKED);
+442 :(before "End Primitive Recipe Checks")
+443 case CURRENT_ROUTINE_IS_UNBLOCKED: {
+444   if (!inst.ingredients.empty()) {
+445   ¦ raise << maybe(get(Recipe, r).name) << "'current-routine-is-unblocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end();
+446   ¦ break;
+447   }
+448   break;
+449 }
+450 :(before "End Primitive Recipe Implementations")
+451 case CURRENT_ROUTINE_IS_UNBLOCKED: {
+452   Current_routine->blocked = false;
+453   break;
+454 }
+455 
+456 //: also allow waiting on a routine to block
+457 //: (just for tests; use wait_for_routine above wherever possible)
+458 
+459 :(scenario wait_for_routine_to_block)
+460 def f1 [
+461   1:num/routine <- start-running f2
+462   wait-for-routine-to-block 1:num/routine
+463   # now wait for f2 to run and modify location 10 before using its value
+464   11:num <- copy 10:num
+465 ]
+466 def f2 [
+467   10:num <- copy 34
+468 ]
+469 +schedule: f1
+470 +run: waiting for routine 2 to block
+471 +schedule: f2
+472 +schedule: waking up routine 1 because routine 2 is blocked
+473 +schedule: f1
+474 # if we got the synchronization wrong we'd be storing 0 in location 11
+475 +mem: storing 34 in location 11
+476 
+477 :(before "End routine Fields")
+478 // only if state == WAITING
+479 int waiting_on_routine_to_block;
+480 :(before "End routine Constructor")
+481 waiting_on_routine_to_block = 0;
+482 
+483 :(before "End Primitive Recipe Declarations")
+484 WAIT_FOR_ROUTINE_TO_BLOCK,
+485 :(before "End Primitive Recipe Numbers")
+486 put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK);
+487 :(before "End Primitive Recipe Checks")
+488 case WAIT_FOR_ROUTINE_TO_BLOCK: {
+489   if (SIZE(inst.ingredients) != 1) {
+490   ¦ raise << maybe(get(Recipe, r).name) << "'wait-for-routine-to-block' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+491   ¦ break;
+492   }
+493   if (!is_mu_number(inst.ingredients.at(0))) {
+494   ¦ raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine-to-block' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
+495   ¦ break;
+496   }
+497   break;
+498 }
+499 :(before "End Primitive Recipe Implementations")
+500 case WAIT_FOR_ROUTINE_TO_BLOCK: {
+501   if (ingredients.at(0).at(0) == Current_routine->id) {
+502   ¦ raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end();
+503   ¦ break;
+504   }
+505   Current_routine->state = WAITING;
+506   Current_routine->waiting_on_routine_to_block = ingredients.at(0).at(0);
+507   trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << " to block" << end();
+508   break;
+509 }
+510 
+511 :(before "End Scheduler State Transitions")
+512 // Wake up any routines waiting for other routines to stop running.
+513 for (int i = 0;  i < SIZE(Routines);  ++i) {
+514   if (Routines.at(i)->state != WAITING) continue;
+515   routine* waiter = Routines.at(i);
+516   if (!waiter->waiting_on_routine_to_block) continue;
+517   int id = waiter->waiting_on_routine_to_block;
+518   assert(id != waiter->id);  // routine can't wait on itself
+519   for (int j = 0;  j < SIZE(Routines);  ++j) {
+520   ¦ const routine* waitee = Routines.at(j);
+521   ¦ if (waitee->id != id) continue;
+522   ¦ if (waitee->state != RUNNING || waitee->blocked) {
+523   ¦ ¦ trace(9999, "schedule") << "waking up routine " << waiter->id << " because routine " << waitee->id << " is blocked" << end();
+524   ¦ ¦ waiter->state = RUNNING;
+525   ¦ ¦ waiter->waiting_on_routine_to_block = 0;
+526   ¦ }
+527   }
+528 }
+529 
+530 //: helper for restarting blocking routines in tests
+531 
+532 :(before "End Primitive Recipe Declarations")
+533 RESTART,
+534 :(before "End Primitive Recipe Numbers")
+535 put(Recipe_ordinal, "restart", RESTART);
+536 :(before "End Primitive Recipe Checks")
+537 case RESTART: {
+538   if (SIZE(inst.ingredients) != 1) {
+539   ¦ raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end();
+540   ¦ break;
+541   }
+542   if (!is_mu_number(inst.ingredients.at(0))) {
+543   ¦ 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();
+544   ¦ break;
+545   }
+546   break;
+547 }
+548 :(before "End Primitive Recipe Implementations")
+549 case RESTART: {
+550   int id = ingredients.at(0).at(0);
+551   for (int i = 0;  i < SIZE(Routines);  ++i) {
+552   ¦ if (Routines.at(i)->id == id) {
+553   ¦ ¦ if (Routines.at(i)->state == WAITING)
+554   ¦ ¦ ¦ Routines.at(i)->state = RUNNING;
+555   ¦ ¦ Routines.at(i)->blocked = false;
+556   ¦ ¦ break;
+557   ¦ }
+558   }
+559   break;
+560 }
+561 
+562 :(scenario cannot_restart_completed_routine)
+563 % Scheduling_interval = 1;
+564 def main [
+565   local-scope
+566   r:num/routine-id <- start-running f
+567   x:num <- copy 0  # wait for f to be scheduled
+568   # r is COMPLETED by this point
+569   restart r  # should have no effect
+570   x:num <- copy 0  # give f time to be scheduled (though it shouldn't be)
+571 ]
+572 def f [
+573   1:num/raw <- copy 1
+574 ]
+575 # shouldn't crash
+576 
+577 :(scenario restart_blocked_routine)
+578 % Scheduling_interval = 1;
+579 def main [
+580   local-scope
+581   r:num/routine-id <- start-running f
+582   wait-for-routine-to-block r  # get past the block in f below
+583   restart r
+584   wait-for-routine-to-block r  # should run f to completion
+585 ]
+586 # function with one block
+587 def f [
+588   current-routine-is-blocked
+589   # 8 instructions of padding, many more than 'main' above
+590   1:num <- add 1:num, 1
+591   1:num <- add 1:num, 1
+592   1:num <- add 1:num, 1
+593   1:num <- add 1:num, 1
+594   1:num <- add 1:num, 1
+595   1:num <- add 1:num, 1
+596   1:num <- add 1:num, 1
+597   1:num <- add 1:num, 1
+598   1:num <- add 1:num, 1
+599 ]
+600 # make sure all of f ran
+601 +mem: storing 8 in location 1
+
+ + + diff --git a/html/076continuation.cc.html b/html/076continuation.cc.html index 3cb2541f..db9ae8c5 100644 --- a/html/076continuation.cc.html +++ b/html/076continuation.cc.html @@ -83,7 +83,7 @@ if ('onhashchange' in window) { 19 Type[continuation].name = "continuation"; 20 21 //: A continuation can be called like a recipe. - 22 :(before "End is_mu_recipe Atom Cases(r)") + 22 :(before "End is_mu_recipe Atom Cases(r)") 23 if (r.type->name == "continuation") return true; 24 25 //: However, it can't be type-checked like most recipes. Pretend it's like a @@ -119,11 +119,11 @@ if ('onhashchange' in window) { 55 23:number <- add 22:number, 1 56 return 23:number 57 ] - 58 # first call of 'g' executes the part before reply-delimited-continuation + 58 # first call of 'g' executes the part before return-continuation-until-mark 59 +mem: storing 77 in location 21 60 +run: {2: "number"} <- copy {5: "literal"} 61 +mem: storing 5 in location 2 - 62 # calls of the continuation execute the part after reply-delimited-continuation + 62 # calls of the continuation execute the part after return-continuation-until-mark 63 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"} 64 +mem: storing 5 in location 22 65 +mem: storing 6 in location 2 @@ -133,9 +133,9 @@ if ('onhashchange' in window) { 69 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"} 70 +mem: storing 7 in location 22 71 +mem: storing 8 in location 2 - 72 # first call of 'g' does not execute the part after reply-delimited-continuation + 72 # first call of 'g' does not execute the part after return-continuation-until-mark 73 -mem: storing 77 in location 22 - 74 # calls of the continuation don't execute the part before reply-delimited-continuation + 74 # calls of the continuation don't execute the part before return-continuation-until-mark 75 -mem: storing 5 in location 21 76 -mem: storing 6 in location 21 77 -mem: storing 7 in location 21 @@ -245,7 +245,7 @@ if ('onhashchange' in window) { 181 ¦ trace("trace") << "calling delimited continuation; growing callstack depth to " << Trace_stream->callstack_depth << end(); 182 ¦ assert(Trace_stream->callstack_depth < 9000); // 9998-101 plus cushion 183 } -184 ++current_step_index(); // skip past the reply-delimited-continuation +184 ++current_step_index(); // skip past the return-continuation-until-mark 185 ingredients.erase(ingredients.begin()); // drop the callee 186 finish_call_housekeeping(to_instruction(caller), ingredients); 187 continue; -- cgit 1.4.1-2-gfad0