https://github.com/akkartik/mu/blob/master/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 i
discard """
  msg: '''61'''
"""

# bug #2297

import tables

proc html5tags*(): TableRef[string, string] =
  var html5tagsCache: Table[string,string]
  if true:
    new(result)
    html5tagsCache = initTable[string, string]()
    html5tagsCache["a"] = "a"
    html5tagsCache["abbr"] = "abbr"
    html5tagsCache["b"] = "b"
    html5tagsCache["element"] = "element"
    html5tagsCache["embed"] = "embed"
    html5tagsCache["fieldset"] = "fieldset"
    html5tagsCache["figcaption"] = "figcaption"
    html5tagsCache["figure"] = "figure"
    html5tagsCache["footer"] = "footer"
    html5tagsCache["header"] = "header"
    html5tagsCache["form"] = "form"
    html5tagsCache["head"] = "head"
    html5tagsCache["hr"] = "hr"
    html5tagsCache["html"] = "html"
    html5tagsCache["iframe"] = "iframe"
    html5tagsCache["img"] = "img"
    html5tagsCache["input"] = "input"
    html5tagsCache["keygen"] = "keygen"
    html5tagsCache["label"] = "label"
    html5tagsCache["legend"] = "legend"
    html5tagsCache["li"] = "li"
    html5tagsCache["link"] = "link"
    html5tagsCache["main"] = "main"
    html5tagsCache["map"] = "map"
    html5tagsCache["menu"] = "menu"
    html5tagsCache["menuitem"] = "menuitem"
    html5tagsCache["meta"] = "meta"
    html5tagsCache["meter"] = "master"
    html5tagsCache["noscript"] = "noscript"
    html5tagsCache["object"] = "object"
    html5tagsCache["ol"] = "ol"
    html5tagsCache["optgroup"] = "optgroup"
    html5tagsCache["option"] = "option"
    html5tagsCache["output"] = "output"
    html5tagsCache["p"] = "p"
    html5tagsCache["pre"] = "pre"
    html5tagsCache["param"] = "param"
    html5tagsCache["progress"] = "progress"
    html5tagsCache["q"] = "q"
    html5tagsCache["rp"] = "rp"
    html5tagsCache["rt"] = "rt"
    html5tagsCache["ruby"] = "ruby"
    html5tagsCache["s"] = "s"
    html5tagsCache["script"] = "script"
    html5tagsCache["select"] = "select"
    html5tagsCache["source"] = "source"
    html5tagsCache["style"] = "style"
    html5tagsCache["summary"] = "summary"
    html5tagsCache["table"] = "table"
    html5tagsCache["tbody"] = "tbody"
    html5tagsCache["thead"] = "thead"
    html5tagsCache["td"] = "td"
    html5tagsCache["th"] = "th"
    html5tagsCache["template"] = "template"
    html5tagsCache["textarea"] = "textarea"
    html5tagsCache["time"] = "time"
    html5tagsCache["title"] = "title"
    html5tagsCache["tr"] = "tr"
    html5tagsCache["track"] = "track"
    html5tagsCache["ul"] = "ul"
    html5tagsCache["video"] = "video"
  result[] = html5tagsCache

static:
  var i = 0
  for key, value in html5tags().pairs():
    inc i
  echo i
); 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/alloc-id, 2:num <- copy 0, 10 266 10:num/alloc-id, 11:num/x, 12:num/y <- copy 0, 34, 35 267 20:location <- get-location 1:&:point/lookup, 0:offset 268 ] 269 +mem: storing 11 in location 20 270 271 :(scenario get_location_indirect_2) 272 def main [ 273 1:num/alloc-id, 2:num <- copy 0, 10 274 10:num/alloc-id, 11:num/x, 12:num/y <- copy 0, 34, 35 275 4:num/alloc-id, 5:num <- copy 0, 20 276 4:&:location/lookup <- get-location 1:&:point/lookup, 0:offset 277 ] 278 +mem: storing 11 in location 21 279 280 //: allow waiting on a routine to complete 281 282 :(scenario wait_for_routine) 283 def f1 [ 284 # add a few routines to run 285 1:num/routine <- start-running f2 286 2:num/routine <- start-running f3 287 wait-for-routine 1:num/routine 288 # now wait for f2 to *complete* and modify location 13 before using its value 289 20:num <- copy 13:num 290 ] 291 def f2 [ 292 10:num <- copy 0 # just padding 293 switch # simulate a block; routine f1 shouldn't restart at this point 294 13:num <- copy 34 295 ] 296 def f3 [ 297 # padding routine just to help simulate the block in f2 using 'switch' 298 11:num <- copy 0 299 12:num <- copy 0 300 ] 301 +schedule: f1 302 +run: waiting for routine 2 303 +schedule: f2 304 +schedule: f3 305 +schedule: f2 306 +schedule: waking up routine 1 307 +schedule: f1 308 # if we got the synchronization wrong we'd be storing 0 in location 20 309 +mem: storing 34 in location 20 310 311 :(before "End routine Fields") 312 // only if state == WAITING 313 int waiting_on_routine; 314 :(before "End routine Constructor") 315 waiting_on_routine = 0; 316 317 :(before "End Primitive Recipe Declarations") 318 WAIT_FOR_ROUTINE, 319 :(before "End Primitive Recipe Numbers") 320 put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE); 321 :(before "End Primitive Recipe Checks") 322 case WAIT_FOR_ROUTINE: { 323 if (SIZE(inst.ingredients) != 1) { 324 raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end(); 325 break; 326 } 327 if (!is_mu_number(inst.ingredients.at(0))) { 328 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(); 329 break; 330 } 331 break; 332 } 333 :(before "End Primitive Recipe Implementations") 334 case WAIT_FOR_ROUTINE: { 335 if (ingredients.at(0).at(0) == Current_routine->id) { 336 raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); 337 break; 338 } 339 Current_routine->state = WAITING; 340 Current_routine->waiting_on_routine = ingredients.at(0).at(0); 341 trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end(); 342 break; 343 } 344 345 :(before "End Scheduler State Transitions") 346 // Wake up any routines waiting for other routines to complete. 347 // Important: this must come after the scheduler loop above giving routines 348 // waiting for locations to change a chance to wake up. 349 for (int i = 0; i < SIZE(Routines); ++i) { 350 if (Routines.at(i)->state != WAITING) continue; 351 routine* waiter = Routines.at(i); 352 if (!waiter->waiting_on_routine) continue; 353 int id = waiter->waiting_on_routine; 354 assert(id != waiter->id); // routine can't wait on itself 355 for (int j = 0; j < SIZE(Routines); ++j) { 356 const routine* waitee = Routines.at(j); 357 if (waitee->id == id && waitee->state != RUNNING && waitee->state != WAITING) { 358 // routine is COMPLETED or DISCONTINUED 359 trace("schedule") << "waking up routine " << waiter->id << end(); 360 waiter->state = RUNNING; 361 waiter->waiting_on_routine = 0; 362 } 363 } 364 } 365 366 //: yield voluntarily to let some other routine run 367 368 :(before "End Primitive Recipe Declarations") 369 SWITCH, 370 :(before "End Primitive Recipe Numbers") 371 put(Recipe_ordinal, "switch", SWITCH); 372 :(before "End Primitive Recipe Checks") 373 case SWITCH: { 374 break; 375 } 376 :(before "End Primitive Recipe Implementations") 377 case SWITCH: { 378 ++current_step_index(); 379 goto stop_running_current_routine; 380 } 381 382 :(scenario switch_preempts_current_routine) 383 def f1 [ 384 start-running f2 385 1:num <- copy 34 386 switch 387 3:num <- copy 36 388 ] 389 def f2 [ 390 2:num <- copy 35 391 ] 392 +mem: storing 34 in location 1 393 # context switch 394 +mem: storing 35 in location 2 395 # back to original thread 396 +mem: storing 36 in location 3 397 398 //:: helpers for manipulating routines in tests 399 //: 400 //: Managing arbitrary scenarios requires the ability to: 401 //: a) check if a routine is blocked 402 //: b) restart a blocked routine ('restart') 403 //: 404 //: A routine is blocked either if it's waiting or if it explicitly signals 405 //: that it's blocked (even as it periodically wakes up and polls for some 406 //: event). 407 //: 408 //: Signalling blockedness might well be a huge hack. But Mu doesn't have Unix 409 //: signals to avoid polling with, because signals are also pretty hacky. 410 411 :(before "End routine Fields") 412 bool blocked; 413 :(before "End routine Constructor") 414 blocked = false; 415 416 :(before "End Primitive Recipe Declarations") 417 CURRENT_ROUTINE_IS_BLOCKED, 418 :(before "End Primitive Recipe Numbers") 419 put(Recipe_ordinal, "current-routine-is-blocked", CURRENT_ROUTINE_IS_BLOCKED); 420 :(before "End Primitive Recipe Checks") 421 case CURRENT_ROUTINE_IS_BLOCKED: { 422 if (!inst.ingredients.empty()) { 423 raise << maybe(get(Recipe, r).name) << "'current-routine-is-blocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end(); 424 break; 425 } 426 break; 427 } 428 :(before "End Primitive Recipe Implementations") 429 case CURRENT_ROUTINE_IS_BLOCKED: { 430 Current_routine->blocked = true; 431 break; 432 } 433 434 :(before "End Primitive Recipe Declarations") 435 CURRENT_ROUTINE_IS_UNBLOCKED, 436 :(before "End Primitive Recipe Numbers") 437 put(Recipe_ordinal, "current-routine-is-unblocked", CURRENT_ROUTINE_IS_UNBLOCKED); 438 :(before "End Primitive Recipe Checks") 439 case CURRENT_ROUTINE_IS_UNBLOCKED: { 440 if (!inst.ingredients.empty()) { 441 raise << maybe(get(Recipe, r).name) << "'current-routine-is-unblocked' should have no ingredients, but got '" << to_original_string(inst) << "'\n" << end(); 442 break; 443 } 444 break; 445 } 446 :(before "End Primitive Recipe Implementations") 447 case CURRENT_ROUTINE_IS_UNBLOCKED: { 448 Current_routine->blocked = false; 449 break; 450 } 451 452 //: also allow waiting on a routine to block 453 //: (just for tests; use wait_for_routine above wherever possible) 454 455 :(scenario wait_for_routine_to_block) 456 def f1 [ 457 1:num/routine <- start-running f2 458 wait-for-routine-to-block 1:num/routine 459 # now wait for f2 to run and modify location 10 before using its value 460 11:num <- copy 10:num 461 ] 462 def f2 [ 463 10:num <- copy 34 464 ] 465 +schedule: f1 466 +run: waiting for routine 2 to block 467 +schedule: f2 468 +schedule: waking up routine 1 because routine 2 is blocked 469 +schedule: f1 470 # if we got the synchronization wrong we'd be storing 0 in location 11 471 +mem: storing 34 in location 11 472 473 :(before "End routine Fields") 474 // only if state == WAITING 475 int waiting_on_routine_to_block; 476 :(before "End routine Constructor") 477 waiting_on_routine_to_block = 0; 478 479 :(before "End Primitive Recipe Declarations") 480 WAIT_FOR_ROUTINE_TO_BLOCK, 481 :(before "End Primitive Recipe Numbers") 482 put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK); 483 :(before "End Primitive Recipe Checks") 484 case WAIT_FOR_ROUTINE_TO_BLOCK: { 485 if (SIZE(inst.ingredients) != 1) { 486 raise << maybe(get(Recipe, r).name) << "'wait-for-routine-to-block' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end(); 487 break; 488 } 489 if (!is_mu_number(inst.ingredients.at(0))) { 490 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(); 491 break; 492 } 493 break; 494 } 495 :(before "End Primitive Recipe Implementations") 496 case WAIT_FOR_ROUTINE_TO_BLOCK: { 497 if (ingredients.at(0).at(0) == Current_routine->id) { 498 raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); 499 break; 500 } 501 Current_routine->state = WAITING; 502 Current_routine->waiting_on_routine_to_block = ingredients.at(0).at(0); 503 trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << " to block" << end(); 504 break; 505 } 506 507 :(before "End Scheduler State Transitions") 508 // Wake up any routines waiting for other routines to stop running. 509 for (int i = 0; i < SIZE(Routines); ++i) { 510 if (Routines.at(i)->state != WAITING) continue; 511 routine* waiter = Routines.at(i); 512 if (!waiter->waiting_on_routine_to_block) continue; 513 int id = waiter->waiting_on_routine_to_block; 514 assert(id != waiter->id); // routine can't wait on itself 515 for (int j = 0; j < SIZE(Routines); ++j) { 516 const routine* waitee = Routines.at(j); 517 if (waitee->id != id) continue; 518 if (waitee->state != RUNNING || waitee->blocked) { 519 trace("schedule") << "waking up routine " << waiter->id << " because routine " << waitee->id << " is blocked" << end(); 520 waiter->state = RUNNING; 521 waiter->waiting_on_routine_to_block = 0; 522 } 523 } 524 } 525 526 //: helper for restarting blocking routines in tests 527 528 :(before "End Primitive Recipe Declarations") 529 RESTART, 530 :(before "End Primitive Recipe Numbers") 531 put(Recipe_ordinal, "restart", RESTART); 532 :(before "End Primitive Recipe Checks") 533 case RESTART: { 534 if (SIZE(inst.ingredients) != 1) { 535 raise << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got '" << to_original_string(inst) << "'\n" << end(); 536 break; 537 } 538 if (!is_mu_number(inst.ingredients.at(0))) { 539 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(); 540 break; 541 } 542 break; 543 } 544 :(before "End Primitive Recipe Implementations") 545 case RESTART: { 546 int id = ingredients.at(0).at(0); 547 for (int i = 0; i < SIZE(Routines); ++i) { 548 if (Routines.at(i)->id == id) { 549 if (Routines.at(i)->state == WAITING) 550 Routines.at(i)->state = RUNNING; 551 Routines.at(i)->blocked = false; 552 break; 553 } 554 } 555 break; 556 } 557 558 :(scenario cannot_restart_completed_routine) 559 % Scheduling_interval = 1; 560 def main [ 561 local-scope 562 r:num/routine-id <- start-running f 563 x:num <- copy 0 # wait for f to be scheduled 564 # r is COMPLETED by this point 565 restart r # should have no effect 566 x:num <- copy 0 # give f time to be scheduled (though it shouldn't be) 567 ] 568 def f [ 569 1:num/raw <- copy 1 570 ] 571 # shouldn't crash 572 573 :(scenario restart_blocked_routine) 574 % Scheduling_interval = 1; 575 def main [ 576 local-scope 577 r:num/routine-id <- start-running f 578 wait-for-routine-to-block r # get past the block in f below 579 restart r 580 wait-for-routine-to-block r # should run f to completion 581 ] 582 # function with one block 583 def f [ 584 current-routine-is-blocked 585 # 8 instructions of padding, many more than 'main' above 586 1:num <- add 1:num, 1 587 1:num <- add 1:num, 1 588 1:num <- add 1:num, 1 589 1:num <- add 1:num, 1 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 ] 596 # make sure all of f ran 597 +mem: storing 8 in location 1