// 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;
use crate::emulator::NO_DEADLINE;
/// 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);
/// 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 {
/// 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", 1_000_000_000),
];
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"
);
}
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);
}
}