Home / Docs / Specification / 27. Tasks and time

27.8 Traces, schedules and equivalence

Release v0.4.0
  1. Traces written as they happen (ADR 0117 rule 10). The root task and the started tasks write their events as they happen; the tasks of together, together for and first of keep theirs until their join, which adopts them as §6 rule 6 and spec/19 §7 rule 2 say, into the task that runs the block. seq numbers the events in the order they are written. An operation's event is written when the operation ends, after the events of the handler code that served it. The events of a block's tasks are numbered when the block's task writes them, after those that started tasks wrote meanwhile.

    • Installations. The root task and the started tasks number the handler instances they install with with, with:<handler>#<n>, run-wide, in the order the installations happen; the tasks of a block keep their numbering until their join, which numbers them as before. Quiet code (spec/26 §6 rule 4) counts none of its installations: each is with:<handler>#q, which a join leaves as it is, so how many it installed never shows in an id (S-41); the operations such an instance serves append no event (#1544). This holds in every edition, the root task's installations included (spec/11 §5).
    • --trace <file>, on the executable (spec/16 §3 rule 4) and on una run, writes the trace to the file as a JSON array as it goes: [ with the first event, each event as it is written, and ] when the run ends, so a finished run's file is the array of spec/11 §5, and a long run's trace does not grow in memory. A file that cannot be made is a usage error, exit code 2, before main starts. una run --json still holds the whole trace in its document.
    • A run that executes no tasks statement has the trace of spec/19 §7 rule 4. A run that does has the order of real time across started tasks, out of model as the order of effects across tasks already is (spec/07 §1).
  2. The interpreter's schedule (ADR 0117 rules 11 and 12). The interpreter stays deterministic for a given host behavior and runs on one thread, but for the helper threads of Http requests in a run that serves live peers (last item). In a run whose program has a tasks statement, the root task and each started task run on una-sys coroutines, one at a time:

    • they wait in one first-in, first-out queue; the task that runs goes on until it parks (a start at its bound, the end of a statement waiting for its tasks), ends, or has passed 1024 check points in its turn while another task is ready, and then goes to the back;
    • a started task joins the back of the queue when it is started, and the task that started it goes on; a parked task joins the back when a task it waits for ends;
    • together, together for and first of run inside the turn of the task that runs them, in index order;
    • check points are each call, each operation, each loop iteration, and each element of a prelude function over a list (map, filter, first_where, fold), counted on Core IR, the same in both engines;
    • a started task's stack is sized from --task-depth, as native code sizes it; host operations run on the interpreter's thread, except an Http request in a run whose serve engine serves live peers (spec/31 §1 rule 10) and whose program has a tasks statement, made while one of the places of §2 rule 3 is free, of the number native code counts: there the request runs on a helper thread while its task parks, with the same outcome, holding that place until it returns; a request that finds no place free runs on the run's thread; nothing interrupts a request in flight but its deadline and, in the body of a for ever, a host stop, so a canceled task's request runs to its deadline, its result dropped and its event showing its own outcome where native code writes interrupted; and the task joins the back of the queue once the request has returned, so the order of the run's tasks also depends on when requests return, as the order of its requests already depends on when peers send them (ADR 0117, amendment of 2026-11-09).
  3. Native code under virtual time (ADR 0117 rule 12). Under --virtual-time, native code follows the interpreter's schedule: one worker, whatever --workers says; the root on a coroutine of it in a program with a tasks statement; the tasks of together, together for and first of one after another, in index order, each to its end, on the turn of the task that runs the block; every check point counted, and the switch after 1024 of them between the root and started tasks; host operations run on the worker. So both engines MUST give the same output, exit status, failure and trace for any run of the constructs of this chapter, tasks included.

    • An executable built with check elision (ADR 0112) refuses --virtual-time: a usage error, exit code 2, before main starts, since a check point compiled away would move the switches. The equivalence tests build with --no-elision.
  4. Native code under the real clock (ADR 0117 rule 2). Started tasks run on --workers workers, pinned, each worker's queue first in, first out; a task's turn ends at a check point once 10 ms have passed since the later of the turn's start and the moment another task became ready on its worker, while that task still waits, through the worker's attention word. When a turn ends MUST depend only on those two moments, kept in nanoseconds of the monotonic clock: the run's slicer starts before its first task runs, whatever the program starts later, and never ticks on a phase of the run, and the time a task ran alone, as the root does before its first start, never shortens the turn a waiting task sees. So whether or when earlier code started a task, and how long it ran, secret code included, never moves the end of a later turn (ADR 0117 rule 2, IF3). A run in which the schedule decides the outcome is compared only for being an outcome the UAM allows under some timing: each task's events and lines in its own order (spec/19 §8 rule 4). The installations of started tasks happen in that order too, so the run-wide numbers of rule 1, with:<handler>#<n>, follow it: two started tasks that both install handlers may interleave their numbers, where the interpreter's schedule gives each task's in turn, and the comparison sets aside one renumbering of the run's installations, never more (#1542): a one-to-one renaming of the native ids onto the interpreter's, which keeps each handler and, within each task, the order of each handler's numbers, and leaves quiet, host and given ids as they are. The two runs need not show the same numbers: an installation whose instance serves no operation has no event, and under the real clock it can take a number before another task's. Under --virtual-time the whole traces are compared, ids included (rule 3).

  5. Check points that labeled data decide (#1684, a conservative rule until an amendment of ADR 0117 makes the switch of rules 2 and 3 independent of them). The switch of rule 2 follows how many check points each task passes, the root task included, which counts its turn from the start of the run, so a count that data above internal decide would order the tasks' later effects by that data, in the interpreter and under --virtual-time the same in every run. In a package whose code holds a tasks statement, that has a serve section, whose driver runs each request's handle as a started task (spec/31 §7 rule 4), or that calls a dependency not checked with it, each of these is U4002 when data above internal decide it, in code that a run of the program can reach (#1707): every function but a private one that only other such functions, or test declarations (example declarations in editions 0.1 and 0.2), call. The roots of that reach are each pub function, which a dependent package or the host can call (every entry, handle, on_stop and [drive] step is pub), and each function that a handler's operation or a lambda calls; each predicate, policy and via, each function of a standard module, each function used as a value, and each function that code outside every function but a test calls, are roots too, defensively: each already has a call edge from the code that reaches it, so they keep the rule from refusing less should an edge be missing; the reach follows the calls of functions in the call graph of ADR 0116 P1, O(F + E log X) for the X tests. una test runs tests, a run of the program never does, so a check point that only a test reaches moves no schedule of the program's started tasks, and the report's information.timing does not list it as a task switch either (security/task_switch_example_only, with its twin security/task_switch_reached):

    • a call of a function written in Una, any function but one of the prelude that takes no function, or of a function value, under a program counter above internal, joined with the effect floor of an operation body (spec/07 §7 rule 4) and, for a function value, with its label, which decides which code runs;
    • an operation under such a program counter;
    • a for, for until or for ever loop whose body runs under such a program counter: the enclosing one joined with the label of the loop's range, list or condition (spec/17 §3, spec/26 §4);
    • a call of map, filter or fold whose arguments' top labels, joined with the program counter, are above internal, and of first_where with every label of its arguments, the labels of the predicate's parameters and result included, since its predicate decides how many elements it visits; the dense map, zip_map, update and fold of spec/29 count as map does, by the top labels of their arguments;
    • a call of a function whose code the label rules do not check, in a standard module other than the prelude, in a dependency not checked with the package, or the via of a policy, with an argument one of whose labels is above internal, those of a function value's parameters and result included;
    • a call of a generic function whose code holds such a check point that only a type parameter's label decides, when one of the labels of its arguments is above internal, those of a function value's parameters and result included, since a function value's result can instantiate a type parameter; or, for a generic function used as a value, that check point itself;
    • the bound of a tasks statement, at most n at once, when the deep label of n is above internal: how many tasks run at once orders their effects too.

    The right operand of and, or and implies runs under the label of the left one, as the if of Core does (spec/09). A recursion needs no item of its own: it ends at a decision, so a depth that labeled data decide puts its recursive call under a raised program counter. stop and failures on labeled data already need a program counter that the loop or the caller starts with (spec/26 §3, spec/07 §3), and skip changes no count. A start under a raised program counter starts a task whose started call is such a check point, so it is U4002 too. The timing floor of a within does not count: a deadline cuts at a check point once the clock has passed it, and the interpreter's clock moves only with the run, never with a count of check points (but under the cost clock of rule 6, a mode for testing). The rule is coarse: a branch whose sides pass as many check points is refused too. It leaves out data at internal, as every request of HttpServer is (spec/31 §1): their count of check points may still order the public effects of started tasks, a known residual of the preview (#1708), open until the project decides between the amendment of ADR 0117 and a rule at public. The report lists each check point of the residual in its information.timing list (spec/13 §6), as {"construct": "task switch", "function": "m.f", "label": "internal", "site": {...}}: every one that the items above would refuse with public in place of internal, and that they do not refuse, so that a reader of the report sees where data at internal can order the effects of the package's tasks. The entries appear once the package is accepted: a package refused for any reason has a report of its diagnostics only. The depth of a started task is a channel of the same kind (#1677). A task that runs past --task-depth ends alone and the run goes on (§7); so does one short of its stack, whose frames' sizes its code fixes, not its data, so that case ends alone at a depth as the first does. What can then follow the data that decided its depth: whether its own later effects happen (prints, writes, operations on a handler's state that later code reads, Http requests a peer sees); its auto-answers, which IF6 bounds (spec/31 §1); the order of other tasks' effects, since a task that ends early frees its place under at most n at once and passes no more check points, which is #1708's residual; and its aborted event and line on standard error, which are the operator's output, out of model as the timing of the run is. The run's exit status does not change. Above internal such a recursion passes a check point under a raised program counter, so this rule is what closes the depth channel above internal (security/task_switch_recursion): an amendment that withdraws or narrows it MUST keep a rule for the depth of started tasks, or #1677 reopens above internal. At internal the channel is a known residual (security/task_depth_internal). A call in the right operand of and, or or implies under a left operand above internal is a check point that rule refuses (security/task_switch_short_circuit); a call with effects never stands there at all, since it must be the whole expression of a statement or let (U3013, security/short_circuit_effect). Its cost is O(1) per check point while the package is checked, and one pass over the recorded sites and generic calls after it for each of the two bounds, with ordered sets: O((sites + calls) log n).

  6. The cost clock (ADR 0117, implementation plan step 7, #973). Under una run --virtual-time --cost-clock (spec/13 §5), the interpreter's virtual clock also moves by one millisecond, one tick, at each check point of rule 2, before the check point reads any deadline; nothing else changes the clock's rules (spec/26 §8). The run's time then follows how much work it did: a within or for ever within deadline passes after as many check points as it has milliseconds, a limit refills as check points pass, and Clock.now reads the run's count of check points plus its waits. So a deadline that a count of check points decides shows in the run's values, and a timing label (§5 rule 8, §6 rule 8, spec/26 §7 rule 5) that misses data deciding that count turns into a difference of values that the security hunt's two-run oracle sees (docs/plan/security-hunt-oracle.md). The schedule of rule 2 is unchanged, and so is first of under virtual time: its branches still run in index order, each to its end. A run under the cost clock is deterministic: the same program and inputs give the same output, failure and trace. It is a mode of the interpreter for testing, not a time of the program: native code does not take it, so it has no equivalence across engines, and una test keeps the plain virtual clock. Its cost is one O(1) addition per check point, only in a run that asks for it.