// Copyright (c) 2026 Rigless Labs.
// SPDX-License-Identifier: MIT OR Apache-2.0
//! The virtual clock every access and every event is stamped with, and the events waiting on it.
//!
//! Every access reaches the bus at an instant of the virtual clock, `VirtualNanos`, which the core's instruction count runs, and a model sees that instant and nothing else about time through the `DeviceContext` every method receives: `now`, `schedule` for an event at an absolute instant, and `raise` and `lower` for the instance's interrupts. An event is a timer on that clock: nothing ticks and nothing polls, the core runs to the earliest event as its deadline, and `Device::on_event` is called at that exact instant with the id `schedule` returned, whether or not the firmware touched the peripheral meanwhile. There is no cancel. A model keeps the id of the event it last scheduled and ignores any other, and an instance asking again for an instant it already has an event at gets that event's id back rather than a second one, so an instant fires once per instance however often it was asked for. Two instances' events at one instant fire in the order they were scheduled, and an instant already passed is the instant of the access or event that asked for it, so every run orders them the same way.
use std::collections::BTreeMap;
/// The nanoseconds in a second of the virtual clock.
pub const NANOS_PER_SECOND: u64 = 1_000_000_000;
/// The deadline of a run given none: 292 years of virtual time, which no run reaches.
///
/// It's the most a signed count of nanoseconds holds, so nothing longer can be asked for.
pub const NO_DEADLINE: VirtualNanos = VirtualNanos(i64::MAX as u64);
/// An instant on the virtual clock, or a distance between two, in nanoseconds.
#[derive(
Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize,
)]
pub struct VirtualNanos(pub u64);
/// Spans of a clock's cycles laid end to end, such as the frames on a busy serial line.
///
/// A span rarely lasts a whole number of nanoseconds, so the run carries what each leaves over
/// into the next and never drifts from the clock, however long it lasts.
#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Run {
/// When the last span ends.
pub ends: VirtualNanos,
// In nanoseconds over the clock's rate.
carry: u64,
}
impl Run {
/// A run whose first span starts at `at`.
pub const fn at(at: VirtualNanos) -> Self {
Self { ends: at, carry: 0 }
}
/// Lays `cycles` of a clock at `hz` after the last span, and returns the whole nanoseconds
/// they took.
///
/// # Panics
///
/// If `hz` is zero, or the span doesn't fit the virtual clock.
pub fn extend(&mut self, cycles: u128, hz: u64) -> u64 {
let numerator = cycles * u128::from(NANOS_PER_SECOND) + u128::from(self.carry);
let hz = u128::from(hz);
let nanos = u64::try_from(numerator / hz).expect("a span fits the virtual clock");
self.carry = u64::try_from(numerator % hz).expect("less than the clock's rate");
self.ends = VirtualNanos(self.ends.0.saturating_add(nanos));
nanos
}
/// Drops what the run carried, which counts cycles of the clock before its rate changed.
pub fn drop_carry(&mut self) {
self.carry = 0;
}
}
/// Names an event to the model that scheduled it, unique within its queue and never reused, a reset
/// that empties the queue included, so an id a model kept from before a reset is never a new event's.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
pub struct EventId(u64);
/// The events waiting on the virtual clock, each an absolute instant and the instance that scheduled it.
///
/// This is a timer list on the virtual clock: nothing ticks and nothing polls, an event
/// fires because the emulator reached its instant, and two instances' events at one instant fire in the order they
/// were scheduled, on every run. There is no cancel. A model keeps the id of the event it last scheduled and
/// ignores any other, and an instance holds at most one event per instant.
#[derive(Debug, Default, serde::Serialize, serde::Deserialize)]
pub(crate) struct EventQueue {
due: BTreeMap<(VirtualNanos, u64), usize>,
next_sequence: u64,
}
impl EventQueue {
/// Drops every event the instance at `owner` scheduled, as its reset does.
pub(crate) fn forget(&mut self, owner: usize) {
self.due.retain(|_, held| *held != owner);
}
/// Adds an event at `at` for the instance at `owner`, or returns the one it already has there.
pub(crate) fn schedule(&mut self, at: VirtualNanos, owner: usize) -> EventId {
// One event per instance per instant. A model whose next instant flips between a near one and
// a far one asks for the far one again on every flip, and with no cancel each ask would pile
// another event on that instant: a free-running counter's overflow gathered one per alarm for
// an hour, and the run that reached it fired them all at once.
let mut same_instant = self.due.range((at, 0)..=(at, u64::MAX));
if let Some((&(_, sequence), _)) = same_instant.find(|&(_, &held)| held == owner) {
return EventId(sequence);
}
let sequence = self.next_sequence;
self.next_sequence += 1;
self.due.insert((at, sequence), owner);
EventId(sequence)
}
/// Goes on counting from where `before` stood, when this queue takes over from it, so no id
/// handed out from `before` is handed out again.
pub(crate) fn continue_from(&mut self, before: &Self) {
self.next_sequence = self.next_sequence.max(before.next_sequence);
}
/// Drops every event waiting, and goes on counting from where it stood.
pub(crate) fn clear(&mut self) {
self.due.clear();
}
/// The instant of the earliest event, if any waits.
pub(crate) fn next_at(&self) -> Option<VirtualNanos> {
self.due.keys().next().map(|(at, _sequence)| *at)
}
/// Removes and returns the earliest event due by `now`.
pub(crate) fn pop_due(&mut self, now: VirtualNanos) -> Option<(EventId, usize, VirtualNanos)> {
let (&(at, _sequence), _owner) = self.due.first_key_value()?;
if at > now {
return None;
}
self.due
.pop_first()
.map(|((at, sequence), owner)| (EventId(sequence), owner, at))
}
}
/// A span of virtual time as `rigless run --until` and the debugger's `monitor until-time` take it: a
/// whole number and its unit, `ns`, `us`, `ms` or `s`, like `13ms`.
#[cfg_attr(
all(emulator_absent, not(feature = "cli"), not(test)),
expect(
dead_code,
reason = "the command and the debugger read it, and Miri builds the crate without either"
)
)]
pub(crate) fn parse_virtual_time(text: &str) -> Result<VirtualNanos, String> {
const UNITS: [(&str, u64); 4] = [
("ns", 1),
("us", 1_000),
("ms", 1_000_000),
("s", NANOS_PER_SECOND),
];
let (digits, scale) = UNITS
.iter()
.find_map(|(unit, scale)| text.strip_suffix(unit).map(|digits| (digits, *scale)))
.ok_or_else(|| format!("{text} has no unit: use ns, us, ms, or s"))?;
let count: u64 = digits
.parse()
.map_err(|error| format!("{digits} is not a whole number: {error}"))?;
let nanos = count
.checked_mul(scale)
.ok_or_else(|| format!("{text} does not fit the virtual clock"))?;
// Past this the emulator reads its deadline as none at all.
if nanos > NO_DEADLINE.0 {
return Err(format!(
"{text} is longer than the virtual clock runs: the most is {} ns",
NO_DEADLINE.0
));
}
Ok(VirtualNanos(nanos))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_duration_parses_with_each_unit_and_refuses_the_rest() {
assert_eq!(parse_virtual_time("5ns"), Ok(VirtualNanos(5)));
assert_eq!(parse_virtual_time("5us"), Ok(VirtualNanos(5_000)));
assert_eq!(parse_virtual_time("5ms"), Ok(VirtualNanos(5_000_000)));
assert_eq!(parse_virtual_time("5s"), Ok(VirtualNanos(5_000_000_000)));
assert!(parse_virtual_time("5").is_err());
assert!(parse_virtual_time("fives").is_err());
assert!(parse_virtual_time("99999999999999999999s").is_err());
assert!(
parse_virtual_time("9223372036854775808ns").is_err(),
"past the longest deadline"
);
}
#[test]
fn a_run_carries_what_each_span_leaves_over() {
const THIRDS: u64 = 3;
let mut run = Run::at(VirtualNanos(0));
assert_eq!(run.extend(1, THIRDS), NANOS_PER_SECOND / THIRDS);
assert_eq!(run.extend(1, THIRDS), NANOS_PER_SECOND / THIRDS);
assert_eq!(
run.extend(1, THIRDS),
NANOS_PER_SECOND / THIRDS + 1,
"three thirds left over make a nanosecond"
);
assert_eq!(run.ends, VirtualNanos(NANOS_PER_SECOND));
run.extend(1, THIRDS);
run.drop_carry();
run.extend(2, THIRDS);
assert_eq!(
run.ends,
VirtualNanos(2 * NANOS_PER_SECOND - 1),
"a dropped carry is lost"
);
}
const EARLY: VirtualNanos = VirtualNanos(100);
const LATE: VirtualNanos = VirtualNanos(200);
const FIRST_OWNER: usize = 1;
const SECOND_OWNER: usize = 2;
#[test]
fn an_instance_asking_again_for_an_instant_it_holds_gets_the_same_event() {
let mut queue = EventQueue::default();
let first = queue.schedule(LATE, FIRST_OWNER);
assert_eq!(
queue.schedule(LATE, FIRST_OWNER),
first,
"the same instant, the same event"
);
let other = queue.schedule(LATE, SECOND_OWNER);
assert_ne!(
other, first,
"another instance's event at that instant is its own"
);
assert_eq!(queue.pop_due(LATE), Some((first, FIRST_OWNER, LATE)));
assert_eq!(queue.pop_due(LATE), Some((other, SECOND_OWNER, LATE)));
assert_eq!(queue.pop_due(LATE), None, "asked for twice, fired once");
assert_ne!(
queue.schedule(LATE, FIRST_OWNER),
first,
"once fired, the instant can be asked for again"
);
}
#[test]
fn events_fire_by_instant_then_by_the_order_scheduled() {
let mut queue = EventQueue::default();
let late = queue.schedule(LATE, FIRST_OWNER);
let early_first = queue.schedule(EARLY, FIRST_OWNER);
let early_second = queue.schedule(EARLY, SECOND_OWNER);
assert_eq!(queue.next_at(), Some(EARLY));
assert_eq!(queue.pop_due(LATE), Some((early_first, FIRST_OWNER, EARLY)));
assert_eq!(
queue.pop_due(LATE),
Some((early_second, SECOND_OWNER, EARLY))
);
// Popped while advancing to LATE, the late event still reports the instant it was scheduled at.
assert_eq!(queue.pop_due(LATE), Some((late, FIRST_OWNER, LATE)));
assert_eq!(queue.pop_due(LATE), None);
assert_eq!(queue.next_at(), None);
}
#[test]
fn nothing_pops_before_its_instant() {
let mut queue = EventQueue::default();
let event = queue.schedule(LATE, FIRST_OWNER);
assert_eq!(queue.pop_due(EARLY), None);
assert_eq!(queue.pop_due(VirtualNanos(LATE.0 - 1)), None);
assert_eq!(queue.pop_due(LATE), Some((event, FIRST_OWNER, LATE)));
}
#[test]
fn ids_are_never_reused() {
let mut queue = EventQueue::default();
let first = queue.schedule(EARLY, FIRST_OWNER);
queue.pop_due(EARLY);
let second = queue.schedule(EARLY, FIRST_OWNER);
assert_ne!(first, second);
}
}