//! A mutex and a bounded channel, for tasks that share data.
//!
//! A `Mutex` guards a value so that one task at a time works on it: `lock`
//! returns a `MutexGuard`, which reads and replaces the value until it is
//! released. `channel` makes a `Channel`, a queue holding at most a fixed
//! number of values, which tasks fill through a `Sender` and empty through a
//! `Receiver`, in the order the values were sent. Every module sees these
//! names without an import, and a module's own definition of one of them
//! shadows the one here.
//!
//! Tasks take turns on one thread, so a task is interrupted only where it
//! awaits; a mutex is for a value that must stay consistent across an
//! `.await`. Copying a `Mutex`, `MutexGuard`, `Channel`, `Sender` or
//! `Receiver`, or passing it to a function, shares it rather than copying it.
//! The methods that lock, set, release, send, receive or close take
//! `mut self`, and need a mutable receiver, such as one held in a `mut`
//! binding.
//!
//! A task waiting for a lock, for room in a channel or for a value yields to
//! the other tasks and tries again, over and over: it keeps the processor
//! busy while it waits, and a wait that can never end, such as for a lock
//! that is never released, goes on forever rather than being reported as a
//! deadlock.
//!
//! A producer task sends values through a channel and closes it; the
//! receiver takes them until `recv` gives `None`:
//!
//! ```
//! async fn produce(mut tx: Sender<Int>) {
//! for i in 1..4 { tx.send(i * 10).await }
//! tx.close() // once the channel is empty, `recv` gives `None`
//! }
//!
//! async fn main() {
//! let ch: Channel<Int> = channel(2)
//! spawn(produce(ch.sender()))
//! let mut rx = ch.receiver()
//! let mut total = 0
//! while true {
//! match rx.recv().await {
//! Some(v) => total = total + v
//! None => break
//! }
//! }
//! assert_eq(total, 60)
//! }
//! ```
// Nova standard library -- synchronisation.
//
// An *async* mutex, which is the primitive a cooperative executor needs. A
// thread mutex would be pointless here: `crates/nova-runtime/src/task.rs`'s
// first line is "A single-threaded cooperative executor". But a task can be
// suspended in the middle of a critical section at any `.await`, and while it
// is suspended another task runs -- so anything whose invariant spans a
// suspension point needs exactly this.
//
// Contention is handled by yielding and retrying rather than by parking. That
// keeps the whole module in Nova with no runtime change, and the cost is
// stated rather than hidden: a waiter stays *runnable*, so `report_deadlock`
// cannot see it and a never-released lock spins instead of being diagnosed.
// See the design doc's ยง5 for the condition that would justify revisiting.
/// A value of type `T` that one task at a time can work on, through a
/// `MutexGuard`.
///
/// `lock` and `try_lock` return a guard, and the guard's `release` unlocks
/// the mutex. Nothing releases a guard for you: one never released leaves the
/// mutex locked for the rest of the program. A mutex is not re-entrant: a
/// task that locks one it already holds waits forever. It makes no fairness
/// guarantee either: when several tasks wait, which one gets the lock next is
/// unspecified.
pub record Mutex<T> { locked: Bool, value: T }
// The right to touch a `Mutex`'s value, and the obligation to release it.
//
// NOT RAII, and not by choice: `Drop` is described in three spec files
// (`12-TYPESYSTEM.md`, `13-RUNTIME.md`, `14-CODEGEN.md`) and implemented in
// none of them -- no handling in nova-typeck, nova-resolver or nova-mir, and
// no `trait Drop` in std/core. Releasing this guard is pure Nova
// (`self.owner.locked = false`), so RAII here would need that *language*
// feature; nothing in the runtime substitutes for it.
//
// ADR 0012 is the precedent for what to do instead, not the reason there is
// no RAII: it chose explicit, idempotent `close` for `File` over a
// collector-based backstop, and accepted a uniform documented leak. So
// release is explicit and idempotent here too, and a guard that is never
// released leaves the mutex locked for the life of the process -- the same
// trade, accepted for the same reason.
//
// (An earlier version of this comment claimed ADR 0012 shows the collector
// "offers no per-object hook". When written, ADR 0012 showed the opposite:
// the hook existed and the ADR named it, and its argument was that the hook
// reported *the dying object's own address*, which tells an `fd`-keyed table
// nothing. Since 2026-10-01 the collector no longer has a per-object hook at
// all (ADR 0020). Either way the argument is about `File`, not about a
// pure-Nova guard, and does not transfer here.)
//
// `released` is what makes that idempotence true rather than merely claimed,
// and `File`'s precedent does not supply it. `File`'s second `close` is safe
// because an `fd` is a key into a runtime table and absence from that table
// *is* closedness (ADR 0012). A guard has no table and no key: `owner` is the
// live mutex itself, because records are reference types
// (`docs/adr/0005-mutable-receivers-and-one-shot-hash.md`), and this compiler
// has no move or linear checking, so a guard stays usable after `release`
// (`crates/nova-cli/tests/run_tests.rs:3916-3919` records the grep behind
// that). An unconditional `self.owner.locked = false` would therefore let a
// stale guard clear `locked` while a *different* task is inside its critical
// section. The flag supplies the missing state directly, so `release` and
// `set` are both no-ops on a released guard -- see both below, and
// `tests/runtime/sync_mutex_stale_guard_cannot_steal.nova` and
// `sync_mutex_stale_guard_cannot_write.nova`, one fixture per use.
//
// Inert against mistakes, not against tampering, and the reason is one fact:
// **Nova enforces no field privacy.** Every hole below follows from it.
// `released` is an ordinary readable, writable field, so `g.released = false`
// on a guard that was genuinely obtained and genuinely released resurrects it,
// and its next `release` frees a lock a different task now holds -- measured.
// That needs nothing but the stale guard itself, which is a *strictly weaker*
// precondition than building `MutexGuard { owner: m, released: false }` from
// scratch (also legal, also measured, and it needs a `Mutex<T>` to name). The
// same fact is why `File { fd: 9999 }` is constructible
// (`docs/adr/0012-file-descriptor-lifecycle.md`), with one difference worth
// stating: a forged `fd` safely misses a table lookup, whereas a forged or
// resurrected guard writes straight to the live mutex. Documented, not
// enforced. `get` is not guarded by the flag at all, deliberately, and gives
// its own reason below.
/// The right to work on a locked `Mutex`'s value, and the duty to release
/// it.
///
/// `get` reads the value and `set` replaces it. Call `release` when done: the
/// mutex stays locked until then. After `release`, `set` and a second
/// `release` do nothing, though `get` still reads the value, unguarded.
pub record MutexGuard<T> { owner: Mutex<T>, released: Bool }
impl<T> Mutex<T> {
/// Returns an unlocked mutex holding `value`.
pub fn new(value: T) -> Mutex<T> { Mutex { locked: false, value: value } }
// Take the flag if it is free. Private: the two public entry points differ
// only in what they do when it is not, and returning a `Bool` is what lets
// `lock`'s `while` condition read the result directly -- `!self.take()`
// rather than an `Option` the loop would have to inspect and discard.
//
// (An earlier version of this comment gave the reason as `Option` having
// "no `unwrap`". That is false: `Option::unwrap` is at
// `std/core/lib.nova:89` and std/core calls it six times, on five lines
// -- 490, 520, 538, 601 and 637, the last of which calls it twice.)
fn take(mut self) -> Bool {
if self.locked { return false }
self.locked = true
true
}
// Take the lock, or report that it is held. The caller that gets `Some`
// receives the guard it needs; the caller that gets `None` has nothing it
// could mistake for one.
/// Locks the mutex and returns a guard if it is free, or returns `None`
/// if it is locked, even by the calling task.
///
/// It is not `async`, and never waits.
pub fn try_lock(mut self) -> Option<MutexGuard<T>> {
if self.take() { Some(MutexGuard { owner: self, released: false }) } else { None }
}
// Take the lock, yielding to every other runnable task until it is free.
//
// `while`, not `loop`: Nova has no `loop` keyword -- `loop {` parses as a
// record literal with `loop` as the type name. `yield_now` re-queues this
// task behind everything currently runnable, so the holder always gets a
// turn and can always release; which *waiter* wins afterwards is
// unspecified, and this mutex makes no fairness guarantee.
/// Locks the mutex, waiting while it is locked, and returns a guard.
///
/// An `async fn`. If the mutex is free, it locks it without suspending;
/// otherwise the calling task yields to the other tasks and tries again
/// until the mutex is released. The wait keeps the processor busy, and
/// goes on forever, with no deadlock reported, if the mutex is never
/// released, as when the calling task already holds it.
///
/// Two tasks adding to one total, each holding the lock across a
/// suspension:
///
/// ```
/// async fn add(mut total: Mutex<Int>, n: Int) {
/// let mut guard = total.lock().await
/// let before = guard.get()
/// yield_now().await // other tasks run here, but none can lock `total`
/// guard.set(before + n)
/// guard.release() // nothing releases a guard for you
/// }
///
/// async fn main() {
/// let mut total = Mutex::new(0)
/// let a = spawn(add(total, 1))
/// let b = spawn(add(total, 2))
/// a.join().await
/// b.join().await
/// assert_eq(total.try_lock().unwrap().get(), 3)
/// }
/// ```
pub async fn lock(mut self) -> MutexGuard<T> {
while !self.take() { yield_now().await }
MutexGuard { owner: self, released: false }
}
}
impl<T> MutexGuard<T> {
// The guarded value. Records and arrays are reference types, so mutating
// the returned value's fields or elements mutates what the mutex holds --
// which is the point. But a `T` with no assignable interior is *copied*
// out, and mutating that copy cannot reach the mutex: `Int`, `Bool`,
// `Float` and `Char` have no fields to assign, and `std/strings` has no
// in-place mutation at all (zero `mut self` methods in its nineteen
// `pub fn`s). Use `set` for those.
//
// Callable after `release`, and unlike `release` and `set` this
// deliberately does *not* return early on `released`. The guard now
// carries the state to detect the case, so the earlier reason -- that the
// language cannot prevent it -- is no longer the reason: the library could
// prevent it and chooses not to. There is nothing to return instead. `get`
// yields a `T`, `T` is generic, and no default exists to invent for it, so
// an early return has no value to hand back. The two alternatives are a
// signature change to `Option<T>`, which every caller would then unwrap,
// and a panic -- and a Nova panic aborts the process rather than unwinding,
// because nothing unwinds across a poll boundary. A stale read is also the
// harmless one of the three: it cannot corrupt the mutex, where a stale
// `set` or `release` writes to it. Documented, not enforced.
/// Returns the guarded value.
///
/// A record or an array is shared rather than copied, so a change to its
/// fields or elements changes the value the mutex holds. A value with
/// nothing to change in place, such as an `Int`, `Float`, `Bool`, `Char`
/// or `String`, comes out as a copy: replace it with `set`. `get` still
/// answers after `release`, though the value is then unguarded.
pub fn get(self) -> T { self.owner.value }
// Replace the guarded value -- the other half of the pair `Vec<T>` already
// ships, `get` at `std/collections/lib.nova:117` with `set` at `:125`, and
// for the same reason: without it a `Mutex<Int>` is a read-only view.
//
// A no-op on a released guard, exactly as `release` is. A stale `set` is
// the worse of the two hazards `released` closes: a stale `release` frees
// a flag another task owns, but a stale `set` writes into the protected
// value while that task is inside its critical section. Pinned by
// `tests/runtime/sync_mutex_stale_guard_cannot_write.nova`; deleting the
// line below fails that fixture and no other.
/// Replaces the guarded value with `v`.
///
/// Does nothing if the guard has been released.
pub fn set(mut self, v: T) {
if self.released { return }
self.owner.value = v
}
// Release the lock. Idempotent -- a second call is a no-op, and `released`
// makes that true rather than only stated: without it this body is an
// unconditional write that would free a lock the caller no longer owns.
/// Unlocks the mutex, so another task can lock it.
///
/// Releasing the same guard again does nothing.
pub fn release(mut self) {
if self.released { return }
self.released = true
self.owner.locked = false
}
}
// ------------------------------------------------------------------ channel
// A fixed-capacity FIFO over a flat array. Private: it exists only to give
// `Channel` its buffer, and `std/collections` has no `Queue` to borrow --
// `Vec::pop` takes from the end, which is LIFO.
//
// `head` is the index of the next value out; `len` is how many are live.
// Capacity lives on `Channel` rather than here, because `data` starts empty
// and so cannot report it until the first send allocates.
//
// INVARIANT: `head >= 0`, `len >= 0`, `cap >= 1`. Every `%` below therefore
// has non-negative operands, which matters because Nova's `%` is a
// TRUNCATING remainder -- `-7 % 3` is `-1`, not `2`. Any operation added
// later that seeks backwards must re-establish this, or the wrap arithmetic
// lands outside the array. `std/core/lib.nova:285` and
// `std/collections/lib.nova:203` carry the same warning for hash bucketing.
record Ring<T> { data: [T], head: Int, len: Int }
/// A first-in, first-out queue of values of type `T` that holds at most a
/// fixed number of them, from `channel`.
///
/// Values go in through a `Sender` and come out through a `Receiver`, in the
/// order they were sent. `sender` and `receiver` make as many of each as are
/// needed, all sharing the one channel. Once a sender closes it, no more
/// values go in, but those already in it can still be received.
pub record Channel<T> { ring: Ring<T>, cap: Int, closed: Bool }
// Two views onto one channel. Records are reference types, so both observe
// every mutation; the split carries intent -- hand `tx` to producers and `rx`
// to consumers -- and not enforcement. Nova enforces no field privacy, and
// that is unenforceable rather than merely unenforced: a field's `vis`
// survives the AST (`crates/nova-ast/src/item.rs:71`) and is dropped at
// AST->HIR lowering (`crates/nova-hir/src/lib.rs:918-923`), so
// `check_field_set` (`crates/nova-typeck/src/check.rs:6214-6272`) has no
// visibility left to check. Three routes, of very unequal reach:
//
// - Forging `Sender { ch: c }` grants NOTHING. The literal needs a
// `Channel<T>` to name, and `sender()`/`receiver()` below are `pub` and
// take a plain `self`, so whoever can name the channel can already obtain
// both handles legitimately.
// - `ch.closed = false` REOPENS a closed channel, from any legitimately-held
// handle, and destroys the one property that gives a consumer loop a
// termination condition: that `recv`'s `None` means closed AND drained.
// `close` only ever sets the flag true, so no API path reaches this -- the
// field is simply ordinary. This is the strongest of the three.
// - Writing `ch.ring.head` or `ch.ring.len` breaks the INVARIANT above that
// the truncating `%` depends on, and reaches it without ever naming the
// non-`pub` `Ring<T>`.
//
// Documented, not prevented, as the standing `MutexGuard` is -- and ranked
// the same way, in `nova-spec/20-STDLIB.md` section 13, under the paragraph
// beginning "Neither flag reaches tampering", where naming forgery alone
// was corrected on 2026-08-21 for understating the reach. An earlier
// version of this comment made exactly that mistake here; corrected
// 2026-08-22. Cited by its opening words, and its LINE NUMBER IS
// DELIBERATELY NOT RECORDED, because it moves: every number this citation
// has ever carried has been wrong, including the one it was written with.
// Grep the quoted phrase.
/// The sending side of a `Channel`, from `Channel::sender`.
///
/// Every `Sender` of a channel sends into the same queue, and `close` on any
/// of them closes the channel for all.
pub record Sender<T> { ch: Channel<T> }
/// The receiving side of a `Channel`, from `Channel::receiver`.
///
/// Every `Receiver` of a channel takes from the same queue, so each value is
/// received once, by whichever receiver takes it first.
pub record Receiver<T> { ch: Channel<T> }
// A bounded channel holding at most `buffer` values.
//
// `buffer < 1` clamps to 1. A zero-capacity rendezvous channel needs a
// handoff protocol that yield-and-retry cannot express without a second wait
// state, and clamping follows `Int::pad`'s precedent of an early return over
// a panic.
//
// The call site must annotate: `let ch: Channel<Int> = channel(2)`. The type
// parameter appears only in the return type, and Nova has no turbofish --
// `channel<Int>(2)` is a parse error, read as two comparisons.
/// Returns a new channel, open and empty, that holds at most `buffer` values.
///
/// A `buffer` below 1 counts as 1. Annotate the binding with the value type,
/// as in `let ch: Channel<Int> = channel(8)`: nothing in the call names it.
/// Room for all `buffer` values is allocated by the first send.
pub fn channel<T>(buffer: Int) -> Channel<T> {
let cap = if buffer < 1 { 1 } else { buffer }
Channel { ring: Ring { data: [], head: 0, len: 0 }, cap: cap, closed: false }
}
impl<T> Channel<T> {
/// Returns a `Sender` for the channel.
pub fn sender(self) -> Sender<T> { Sender { ch: self } }
/// Returns a `Receiver` for the channel.
pub fn receiver(self) -> Receiver<T> { Receiver { ch: self } }
// Enqueue, or report refusal. Private: `Sender::try_send` is the public
// door. Returns false when closed and when full, which is why the async
// `send` must re-check `closed` itself to tell the two apart.
fn push(mut self, v: T) -> Bool {
if self.closed { return false }
if self.ring.len == self.cap { return false }
if self.ring.data.len() == 0 {
// First send. `[fill; n]` needs a value of `T` and a fresh
// channel has none, so allocation waits for one -- the same trick
// `Vec::push` uses to grow. Every slot holds `v` until
// overwritten, so the channel briefly retains up to `cap`
// references to the first value sent.
self.ring.data = [v; self.cap]
self.ring.len = 1
return true
}
self.ring.data[(self.ring.head + self.ring.len) % self.cap] = v
self.ring.len = self.ring.len + 1
true
}
// Dequeue, or None when empty. Says nothing about `closed` -- that
// distinction belongs to `Receiver::recv`.
fn pop(mut self) -> Option<T> {
if self.ring.len == 0 { return None }
let v = self.ring.data[self.ring.head]
self.ring.head = (self.ring.head + 1) % self.cap
self.ring.len = self.ring.len - 1
Some(v)
}
}
impl<T> Sender<T> {
// Send if there is room. False when the channel is full OR closed; a
// caller that needs to distinguish them should use `send`, which returns
// false only for closed.
/// Sends `v` and returns `true` if the channel has room, or returns
/// `false` without sending it if the channel is full or closed.
///
/// It is not `async`, and never waits. To tell a full channel from a
/// closed one, use `send`.
pub fn try_send(mut self, v: T) -> Bool { self.ch.push(v) }
// Refuse all further sends. Buffered values stay readable, so a producer
// may close the instant it stops producing and the consumer still drains.
// Idempotent: a second call sets an already-set flag.
/// Closes the channel: later sends, through any sender, return `false`.
///
/// Values already in the channel stay there for the receivers, whose
/// `recv` returns `None` once they are all taken. Closing a closed channel
/// does nothing. Nothing closes a channel for you: close it when done
/// sending, or a receiver waiting in `recv` waits forever.
pub fn close(mut self) { self.ch.closed = true }
// Send, waiting while the channel is full. Returns false only when the
// channel is closed -- unlike `try_send`, which also returns false when
// merely full.
//
// Waiting is `yield_now`, not parking, which keeps this module in Nova
// with no executor change (ADR 0016 made the same call for `Mutex`). The
// cost is stated rather than hidden: a waiter stays *runnable*, so
// `report_deadlock` cannot see it, and a producer blocked on a channel
// nobody drains spins instead of being diagnosed.
/// Sends `v`, waiting while the channel is full, and returns `true` once
/// it is in, or `false`, without sending it, if the channel is closed.
///
/// An `async fn`. If the channel has room, it sends without suspending;
/// otherwise the calling task yields to the other tasks and tries again
/// until there is room or the channel is closed. The wait keeps the
/// processor busy, and goes on forever, with no deadlock reported, if no
/// task ever takes a value out or closes the channel.
pub async fn send(mut self, v: T) -> Bool {
while !self.ch.push(v) {
if self.ch.closed { return false }
yield_now().await
}
true
}
}
impl<T> Receiver<T> {
// Take a value if one is buffered. None means empty, and says nothing
// about whether more will arrive -- `recv` is what distinguishes those.
/// Takes the oldest value in the channel, or returns `None` if it is
/// empty, whether or not it is closed.
///
/// It is not `async`, and never waits.
pub fn try_recv(mut self) -> Option<T> { self.ch.pop() }
// Take the next value, waiting while the channel is empty and open.
//
// None means closed AND drained, never merely empty. That is the whole
// reason `close` is explicit: `Drop` is specified in three spec files and
// implemented in none, so nothing closes a channel on the producer's
// behalf, and without this distinction a consumer loop could not
// terminate.
//
// Buffered values are drained before the close is reported, because `pop`
// is tried before `closed` is read on every iteration.
/// Takes the oldest value in the channel, waiting while it is empty and
/// open, or returns `None` once it is closed and empty.
///
/// An `async fn`. If a value is there, it takes it without suspending;
/// otherwise the calling task yields to the other tasks and tries again.
/// The values still in a closed channel are received before `None`. The
/// wait keeps the processor busy, and goes on forever, with no deadlock
/// reported, if no task ever sends a value or closes the channel.
pub async fn recv(mut self) -> Option<T> {
let mut out = self.ch.pop()
while out.is_none() {
if self.ch.closed { return None }
yield_now().await
out = self.ch.pop()
}
out
}
}