use anyhow::{anyhow, bail};
use crate::core::registry::SourceId;
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum TriggerSpec {
#[cfg(unix)]
Fifo(std::path::PathBuf),
File(std::path::PathBuf),
#[cfg(unix)]
Fd(i32),
}
impl std::fmt::Display for TriggerSpec {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
#[cfg(unix)]
TriggerSpec::Fifo(path) => write!(f, "fifo:{}", path.display()),
TriggerSpec::File(path) => write!(f, "file:{}", path.display()),
#[cfg(unix)]
TriggerSpec::Fd(n) => write!(f, "fd:{n}"),
}
}
}
#[cfg(unix)]
const FD_SETSIZE: i32 = 1024;
pub fn parse_trigger(s: &str) -> anyhow::Result<TriggerSpec> {
let teach = || anyhow!("invalid trigger {s:?}: expected fifo:PATH, file:PATH, or fd:N");
let Some((scheme, rest)) = s.split_once(':') else {
return Err(teach());
};
if rest.is_empty() {
return Err(teach());
}
match scheme {
"file" => Ok(TriggerSpec::File(std::path::PathBuf::from(rest))),
#[cfg(unix)]
"fifo" => Ok(TriggerSpec::Fifo(std::path::PathBuf::from(rest))),
#[cfg(unix)]
"fd" => {
let n: i32 = rest
.parse()
.map_err(|_| anyhow!("invalid trigger {s:?}: fd:N takes a number"))?;
if n < 0 {
bail!("invalid trigger {s:?}: fd:N takes a non-negative number");
}
if n >= FD_SETSIZE {
bail!(
"fd:{n} is out of range for select(2); descriptors must be below {FD_SETSIZE}"
);
}
Ok(TriggerSpec::Fd(n))
}
#[cfg(windows)]
"fifo" | "fd" => {
bail!("{scheme}: triggers are unix-only; use file:PATH")
}
_ => Err(teach()),
}
}
pub struct DebounceGate {
window: std::time::Duration,
deadline: Option<std::time::Instant>,
}
impl DebounceGate {
pub fn new(window: std::time::Duration) -> DebounceGate {
DebounceGate {
window,
deadline: None,
}
}
pub fn fire(&mut self, now: std::time::Instant) {
if self.deadline.is_none() {
self.deadline = Some(now + self.window);
}
}
pub fn due(&mut self, now: std::time::Instant) -> bool {
if self.deadline.is_some_and(|deadline| now >= deadline) {
self.deadline = None;
true
} else {
false
}
}
}
pub struct MtimeWatch {
path: std::path::PathBuf,
last: Option<Fingerprint>,
}
type Fingerprint = Option<std::time::SystemTime>;
impl MtimeWatch {
pub fn new(path: std::path::PathBuf) -> MtimeWatch {
MtimeWatch { path, last: None }
}
pub fn fired(&mut self) -> bool {
let current = fingerprint(&self.path);
let changed = self.last.is_some_and(|last| last != current);
self.last = Some(current);
changed
}
}
fn fingerprint(path: &std::path::Path) -> Fingerprint {
let meta = std::fs::metadata(path).ok()?;
let mut newest = meta.modified().ok()?;
if meta.is_dir() {
for entry in std::fs::read_dir(path).ok()?.flatten() {
if let Ok(modified) = entry.metadata().and_then(|m| m.modified()) {
newest = newest.max(modified);
}
}
}
Some(newest)
}
pub struct MtimeWatchSet(Vec<MtimeWatch>);
impl MtimeWatchSet {
pub fn new(paths: Vec<std::path::PathBuf>) -> MtimeWatchSet {
MtimeWatchSet(paths.into_iter().map(MtimeWatch::new).collect())
}
pub fn fired(&mut self) -> bool {
let mut any = false;
for watch in &mut self.0 {
any |= watch.fired();
}
any
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct PathStamp(Fingerprint);
pub fn stamps(paths: &[std::path::PathBuf]) -> Vec<(std::path::PathBuf, PathStamp)> {
paths
.iter()
.map(|path| (path.clone(), PathStamp(fingerprint(path))))
.collect()
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct BracketId(pub u64);
#[derive(Clone)]
pub struct Bracket {
pub id: BracketId,
pub source: SourceId,
pub opened: std::time::Instant,
pub closed: Option<std::time::Instant>,
pub open_stamps: Vec<(std::path::PathBuf, PathStamp)>,
pub close_stamps: Vec<(std::path::PathBuf, PathStamp)>,
}
pub struct Change {
pub containing: Vec<(SourceId, Option<std::time::Duration>)>,
}
pub struct PathLedger {
paths: Vec<std::path::PathBuf>,
seen: std::collections::HashMap<std::path::PathBuf, PathStamp>,
changes: std::collections::HashMap<std::path::PathBuf, Vec<Observed>>,
}
struct Observed {
at: std::time::Instant,
containing: Vec<(SourceId, BracketId)>,
}
impl PathLedger {
pub fn new(paths: Vec<std::path::PathBuf>) -> PathLedger {
let mut paths = paths;
paths.sort();
paths.dedup();
let seen = stamps(&paths).into_iter().collect();
PathLedger {
paths,
seen,
changes: std::collections::HashMap::new(),
}
}
pub fn observe(&mut self, now: std::time::Instant, brackets: &[(SourceId, BracketId)]) {
for (path, stamp) in stamps(&self.paths) {
if self.moved(&path, stamp) {
self.record(path, now, brackets.to_vec());
}
}
}
pub fn observe_bracket(&mut self, bracket: &Bracket, others: &[(SourceId, BracketId)]) {
let Some(closed) = bracket.closed else {
return; };
let mut containing = vec![(bracket.source, bracket.id)];
for (source, other) in others {
if !containing.iter().any(|(s, _)| s == source) {
containing.push((*source, *other));
}
}
let before: std::collections::HashMap<_, _> = bracket
.open_stamps
.iter()
.map(|(path, stamp)| (path.clone(), *stamp))
.collect();
for (path, stamp) in &bracket.close_stamps {
if before.get(path) == Some(stamp) {
continue;
}
if self.moved(path, *stamp) {
self.record(path.clone(), closed, containing.clone());
}
}
}
pub fn evict(&mut self, now: std::time::Instant, window: std::time::Duration) {
let Some(cutoff) = now.checked_sub(window) else {
return;
};
for changes in self.changes.values_mut() {
changes.retain(|change| change.at >= cutoff);
}
}
pub fn exogenous(&self, path: &std::path::Path) -> usize {
self.raw(path)
.iter()
.filter(|change| change.containing.is_empty())
.count()
}
pub fn changes(&self, path: &std::path::Path, log: &WindowLog) -> Vec<Change> {
self.raw(path)
.iter()
.map(|observed| Change {
containing: observed
.containing
.iter()
.map(|(source, id)| (*source, log.width_of(*id)))
.collect(),
})
.collect()
}
fn raw(&self, path: &std::path::Path) -> &[Observed] {
self.changes.get(path).map_or(&[], Vec::as_slice)
}
fn moved(&mut self, path: &std::path::Path, stamp: PathStamp) -> bool {
match self.seen.get(path) {
Some(last) if *last == stamp => false,
_ => {
self.seen.insert(path.to_path_buf(), stamp);
true
}
}
}
#[cfg(test)]
pub fn inject(
&mut self,
path: &std::path::Path,
at: std::time::Instant,
containing: Vec<(SourceId, BracketId)>,
) {
self.record(path.to_path_buf(), at, containing);
}
fn record(
&mut self,
path: std::path::PathBuf,
at: std::time::Instant,
containing: Vec<(SourceId, BracketId)>,
) {
self.changes
.entry(path)
.or_default()
.push(Observed { at, containing });
}
}
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub struct TriggerKey(pub String);
pub struct Arrival {
pub trigger: TriggerKey,
pub observation: Observation,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Observation {
pub empty_since: Option<std::time::Instant>,
pub observed_at: std::time::Instant,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum TemporalCoverage {
Disjoint,
Covered(Vec<(SourceId, Option<std::time::Duration>)>),
Ambiguous,
}
impl TemporalCoverage {
pub fn is_disjoint(&self) -> bool {
matches!(self, TemporalCoverage::Disjoint)
}
}
pub struct WindowLog {
window: std::time::Duration,
next_id: u64,
brackets: Vec<Bracket>,
respawns: Vec<(SourceId, std::time::Instant)>,
arrivals: Vec<Arrival>,
overflows: Vec<std::time::Instant>,
}
impl WindowLog {
pub fn new(window: std::time::Duration) -> WindowLog {
WindowLog {
window,
next_id: 0,
brackets: Vec::new(),
respawns: Vec::new(),
arrivals: Vec::new(),
overflows: Vec::new(),
}
}
pub fn open_bracket(
&mut self,
source: SourceId,
at: std::time::Instant,
open_stamps: Vec<(std::path::PathBuf, PathStamp)>,
) -> BracketId {
let id = BracketId(self.next_id);
self.next_id += 1;
self.brackets.push(Bracket {
id,
source,
opened: at,
closed: None,
open_stamps,
close_stamps: Vec::new(),
});
id
}
pub fn classify(&self, observation: &Observation) -> TemporalCoverage {
let Some(from) = observation.empty_since else {
return TemporalCoverage::Ambiguous;
};
let to = observation.observed_at;
type Span = (
std::time::Instant,
Option<std::time::Instant>,
SourceId,
Option<std::time::Duration>,
);
let mut spans: Vec<Span> = self
.brackets
.iter()
.map(|b| (b.opened, b.closed, b.source, b.width()))
.filter(|(open, closed, _, _)| closed.is_none_or(|close| close > from) && *open <= to)
.collect();
if spans.is_empty() {
let touching = self
.brackets
.iter()
.any(|b| b.closed.is_none_or(|close| close >= from) && b.opened <= to);
return if touching {
TemporalCoverage::Ambiguous
} else {
TemporalCoverage::Disjoint
};
}
spans.sort_by_key(|(open, _, _, _)| *open);
let mut frontier = from;
let mut unbounded = false;
let mut contributors: Vec<(SourceId, Option<std::time::Duration>)> = Vec::new();
for (open, closed, source, width) in spans {
if !unbounded && open > frontier {
return TemporalCoverage::Ambiguous; }
match closed {
None => unbounded = true,
Some(close) if close > frontier => frontier = close,
Some(_) => {}
}
contributors.push((source, width));
}
if !unbounded && frontier <= to {
return TemporalCoverage::Ambiguous; }
TemporalCoverage::Covered(contributors)
}
pub fn close_bracket(
&mut self,
id: BracketId,
at: std::time::Instant,
close_stamps: Vec<(std::path::PathBuf, PathStamp)>,
) -> Option<&Bracket> {
let bracket = self.brackets.iter_mut().find(|b| b.id == id)?;
bracket.closed = Some(at);
bracket.close_stamps = close_stamps;
Some(bracket)
}
pub fn record_respawn(&mut self, source: SourceId, at: std::time::Instant) {
self.respawns.push((source, at));
}
#[cfg_attr(windows, allow(dead_code))]
pub fn observe_arrival(&mut self, trigger: TriggerKey, observation: Observation) {
self.arrivals.push(Arrival {
trigger,
observation,
});
}
#[cfg_attr(windows, allow(dead_code))]
pub fn record_overflow(&mut self, at: std::time::Instant) {
self.overflows.push(at);
}
pub fn respawns_in_window(&self, source: SourceId, now: std::time::Instant) -> usize {
let cutoff = self.cutoff(now);
self.respawns
.iter()
.filter(|(id, at)| *id == source && cutoff.is_none_or(|c| *at >= c))
.count()
}
pub fn busy_fraction(&self, now: std::time::Instant) -> f64 {
let Some(start) = self.cutoff(now) else {
return 0.0;
};
let mut spans: Vec<(std::time::Instant, std::time::Instant)> = self
.brackets
.iter()
.map(|b| (b.opened.max(start), b.end_or(now).min(now)))
.filter(|(from, to)| to > from)
.collect();
spans.sort_by_key(|(from, _)| *from);
let mut busy = std::time::Duration::ZERO;
let mut merged: Option<(std::time::Instant, std::time::Instant)> = None;
for (from, to) in spans {
match merged {
Some((m_from, m_to)) if from <= m_to => merged = Some((m_from, m_to.max(to))),
Some((m_from, m_to)) => {
busy += m_to.duration_since(m_from);
merged = Some((from, to));
}
None => merged = Some((from, to)),
}
}
if let Some((m_from, m_to)) = merged {
busy += m_to.duration_since(m_from);
}
busy.as_secs_f64() / self.window.as_secs_f64()
}
#[allow(dead_code)]
pub fn covering(&self, at: std::time::Instant) -> Vec<(SourceId, std::time::Duration)> {
self.brackets
.iter()
.filter(|b| b.closed.is_some() && b.spans(at))
.map(|b| (b.source, b.width().unwrap_or_default()))
.collect()
}
pub fn overlapping(&self, bracket: &Bracket) -> Vec<(SourceId, BracketId)> {
let Some(closed) = bracket.closed else {
return Vec::new();
};
self.brackets
.iter()
.filter(|b| b.id != bracket.id)
.filter(|b| b.closed.is_none_or(|end| end >= bracket.opened) && b.opened <= closed)
.map(|b| (b.source, b.id))
.collect()
}
pub fn width_of(&self, id: BracketId) -> Option<std::time::Duration> {
self.brackets.iter().find(|b| b.id == id)?.width()
}
pub fn any_open(&self, at: std::time::Instant) -> bool {
self.brackets
.iter()
.any(|b| b.closed.is_none() && b.opened <= at)
}
pub fn arrivals(&self, trigger: &TriggerKey) -> Vec<&Arrival> {
self.arrivals
.iter()
.filter(|a| a.trigger == *trigger)
.collect()
}
pub fn nearest_bracket_gap(&self, at: std::time::Instant) -> Option<(SourceId, f64)> {
self.brackets
.iter()
.filter_map(|b| {
if at < b.opened {
let ms = b.opened.duration_since(at).as_secs_f64() * 1000.0;
return Some((b.source, -ms));
}
let closed = b.closed?;
Some((
b.source,
at.saturating_duration_since(closed).as_secs_f64() * 1000.0,
))
})
.min_by(|(_, a), (_, b)| a.abs().total_cmp(&b.abs()))
}
pub fn bracket_count(&self) -> usize {
self.brackets.len()
}
pub fn bracket_widths_ms(&self) -> Option<(f64, f64, f64)> {
let mut widths: Vec<f64> = self
.brackets
.iter()
.filter_map(|b| Some(b.width()?.as_secs_f64() * 1000.0))
.collect();
if widths.is_empty() {
return None;
}
widths.sort_by(f64::total_cmp);
Some((
widths[0],
widths[widths.len() / 2],
widths[widths.len() - 1],
))
}
pub fn arrival_gap_ms(&self, trigger: &TriggerKey) -> Option<f64> {
let ats: Vec<std::time::Instant> = self
.arrivals
.iter()
.filter(|a| a.trigger == *trigger)
.map(|a| a.observation.observed_at)
.collect();
if ats.len() < 2 {
return None;
}
let mut gaps: Vec<f64> = ats
.windows(2)
.map(|w| w[1].saturating_duration_since(w[0]).as_secs_f64() * 1000.0)
.collect();
gaps.sort_by(f64::total_cmp);
Some(gaps[gaps.len() / 2])
}
pub fn evidence_lost(&self, now: std::time::Instant) -> bool {
let cutoff = self.cutoff(now);
self.overflows
.iter()
.any(|at| cutoff.is_none_or(|c| *at >= c))
}
pub fn evict(&mut self, now: std::time::Instant) {
let Some(cutoff) = self.cutoff(now) else {
return;
};
self.respawns.retain(|(_, at)| *at >= cutoff);
self.overflows.retain(|at| *at >= cutoff);
self.arrivals
.retain(|a| a.observation.observed_at >= cutoff);
let reach = self
.arrivals
.iter()
.map(|a| {
a.observation
.empty_since
.unwrap_or(a.observation.observed_at)
})
.min();
self.brackets
.retain(|b| b.end_or(now) >= cutoff || reach.is_some_and(|from| b.end_or(now) >= from));
}
fn cutoff(&self, now: std::time::Instant) -> Option<std::time::Instant> {
now.checked_sub(self.window)
}
}
impl Bracket {
pub fn width(&self) -> Option<std::time::Duration> {
Some(self.closed?.saturating_duration_since(self.opened))
}
fn end_or(&self, now: std::time::Instant) -> std::time::Instant {
self.closed.unwrap_or(now)
}
#[allow(dead_code)]
fn spans(&self, at: std::time::Instant) -> bool {
self.opened <= at && self.closed.is_none_or(|closed| closed >= at)
}
}
pub struct LoopSuspicion {
pub window: std::time::Duration,
pub min_respawns: usize,
pub abstain_at_or_above: f64,
pub explain: bool,
}
impl Default for LoopSuspicion {
fn default() -> LoopSuspicion {
LoopSuspicion {
window: std::time::Duration::from_secs(30),
min_respawns: 50,
abstain_at_or_above: 0.5,
explain: false,
}
}
}
pub struct PaneWindow<'a> {
pub source: SourceId,
pub trigger_respawns: usize,
pub watched: &'a [std::path::PathBuf],
pub readers: &'a [TriggerKey],
}
pub struct Verdict {
pub panes: Vec<SourceId>,
#[allow(dead_code)]
pub ordered: Option<Vec<SourceId>>,
pub abstained: bool,
pub why: Option<String>,
}
impl LoopSuspicion {
pub fn evaluate(
&self,
now: std::time::Instant,
ledger: &PathLedger,
log: &WindowLog,
panes: &[PaneWindow<'_>],
) -> Verdict {
let mut why = self
.explain
.then(|| self.explain_inputs(now, ledger, log, panes));
if log.evidence_lost(now) || log.busy_fraction(now) >= self.abstain_at_or_above {
return Verdict {
panes: Vec::new(),
ordered: None,
abstained: true,
why: why.map(|mut w| {
w.push_str(" | c3 ABSTAIN");
w
}),
};
}
let candidates: Vec<&PaneWindow<'_>> = panes
.iter()
.filter(|pane| pane.trigger_respawns >= self.min_respawns)
.filter(|pane| self.closed_everywhere(ledger, log, pane))
.collect();
let mut edges: Vec<(SourceId, SourceId)> = Vec::new();
let mut ambiguities: Vec<(Vec<SourceId>, SourceId)> = Vec::new();
for pane in &candidates {
for path in pane.watched {
let credited = credit(&ledger.changes(path, log));
Self::add(&mut edges, &mut ambiguities, &credited, pane.source);
}
for key in pane.readers {
let changes = Self::arrival_changes(log, key);
let credited = credit(&changes);
Self::add(&mut edges, &mut ambiguities, &credited, pane.source);
}
}
let mut merged: Vec<Vec<SourceId>> = Vec::new();
for (group, _) in &ambiguities {
if merged.contains(group) {
continue;
}
let mut watchers: Vec<SourceId> = ambiguities
.iter()
.filter(|(other, _)| other == group)
.map(|(_, watcher)| *watcher)
.collect();
watchers.sort();
watchers.dedup();
if watchers.len() >= 2 {
merged.push(group.clone());
}
}
let implicated = on_a_cycle(&candidates, &edges, &merged);
let precise = merged.iter().all(|group| group.len() <= 1);
if let Some(w) = why.as_mut() {
use std::fmt::Write as _;
let _ = write!(
w,
" | cand={:?} edges={:?} ambig={:?} merged={:?}",
candidates.iter().map(|c| c.source.0).collect::<Vec<_>>(),
edges.iter().map(|(a, b)| (a.0, b.0)).collect::<Vec<_>>(),
ambiguities
.iter()
.map(|(g, w)| (ids(g), w.0))
.collect::<Vec<_>>(),
merged.iter().map(|g| ids(g)).collect::<Vec<_>>(),
);
}
if implicated.is_empty() {
let undecidable = candidates.iter().any(|pane| {
pane.readers.iter().any(|key| {
let arrivals = log.arrivals(key);
!arrivals.is_empty()
&& arrivals.iter().all(|a| {
matches!(log.classify(&a.observation), TemporalCoverage::Ambiguous)
})
})
});
if undecidable {
return Verdict {
panes: Vec::new(),
ordered: None,
abstained: true,
why: why.map(|mut w| {
w.push_str(" | c4 ABSTAIN (all reader evidence ambiguous)");
w
}),
};
}
}
Verdict {
ordered: (precise && !implicated.is_empty()).then(|| implicated.clone()),
panes: implicated,
abstained: false,
why,
}
}
fn explain_inputs(
&self,
now: std::time::Instant,
ledger: &PathLedger,
log: &WindowLog,
panes: &[PaneWindow<'_>],
) -> String {
use std::fmt::Write as _;
let mut w = format!(
"busy={:.3} lost={} brk={}",
log.busy_fraction(now),
u8::from(log.evidence_lost(now)),
log.bracket_count(),
);
if let Some((min, med, max)) = log.bracket_widths_ms() {
let _ = write!(w, " brkms={min:.2}/{med:.2}/{max:.2}");
}
for pane in panes {
for key in pane.readers {
if let Some(gap) = log.arrival_gap_ms(key) {
let _ = write!(w, " gap{}={gap:.1}", pane.source.0);
}
}
}
for pane in panes {
let exogenous: usize = pane.watched.iter().map(|p| ledger.exogenous(p)).sum();
let (mut arrivals, mut uncontained, mut deferred) = (0usize, 0usize, 0usize);
let mut gaps: Vec<String> = Vec::new();
for key in pane.readers {
for arrival in log.arrivals(key) {
arrivals += 1;
match log.classify(&arrival.observation) {
TemporalCoverage::Covered(contributors) => {
deferred += usize::from(contributors.iter().any(|(_, w)| w.is_none()));
}
TemporalCoverage::Ambiguous => {}
TemporalCoverage::Disjoint => {
uncontained += 1;
gaps.push(
match log.nearest_bracket_gap(arrival.observation.observed_at) {
Some((source, ms)) => format!("s{}{ms:+.1}", source.0),
None => "nobrackets".to_string(),
},
);
}
}
}
}
let _ = write!(
w,
" | s{} resp={}/{} exo={} arr={arrivals}/unc={uncontained}/def={deferred} closed={}",
pane.source.0,
pane.trigger_respawns,
self.min_respawns,
exogenous,
u8::from(self.closed_everywhere(ledger, log, pane)),
);
if !gaps.is_empty() {
let _ = write!(w, " uncgap=[{}]", gaps.join(","));
}
}
w
}
fn closed_everywhere(
&self,
ledger: &PathLedger,
log: &WindowLog,
pane: &PaneWindow<'_>,
) -> bool {
let files_closed = pane.watched.iter().all(|p| ledger.exogenous(p) == 0);
let readers_closed = pane.readers.iter().all(|key| {
log.arrivals(key)
.iter()
.all(|arrival| !log.classify(&arrival.observation).is_disjoint())
});
let watches_something = !pane.watched.is_empty() || !pane.readers.is_empty();
watches_something && files_closed && readers_closed
}
fn arrival_changes(log: &WindowLog, key: &TriggerKey) -> Vec<Change> {
log.arrivals(key)
.iter()
.map(|arrival| match log.classify(&arrival.observation) {
TemporalCoverage::Covered(contributors) => Change {
containing: contributors,
},
TemporalCoverage::Disjoint | TemporalCoverage::Ambiguous => Change {
containing: Vec::new(),
},
})
.collect()
}
fn add(
edges: &mut Vec<(SourceId, SourceId)>,
merged: &mut Vec<(Vec<SourceId>, SourceId)>,
credited: &[SourceId],
watcher: SourceId,
) {
let ambiguous = credited.len() > 1;
for writer in credited {
if ambiguous && *writer == watcher {
continue;
}
edges.push((*writer, watcher));
}
if ambiguous {
merged.push((credited.to_vec(), watcher));
}
}
}
fn ids(group: &[SourceId]) -> Vec<usize> {
group.iter().map(|s| s.0).collect()
}
fn credit(changes: &[Change]) -> Vec<SourceId> {
if changes.is_empty() {
return Vec::new();
}
let mut sources: Vec<SourceId> = changes
.iter()
.flat_map(|change| change.containing.iter().map(|(id, _)| *id))
.collect();
sources.sort();
sources.dedup();
let eligible: Vec<SourceId> = sources
.into_iter()
.filter(|id| {
let covered = changes
.iter()
.filter(|c| c.containing.iter().any(|(s, _)| s == id))
.count();
covered * 2 > changes.len()
})
.collect();
if eligible.is_empty() {
return Vec::new();
}
let medians: Vec<(SourceId, std::time::Duration)> = eligible
.into_iter()
.filter_map(|id| median_width(changes, id).map(|width| (id, width)))
.collect();
let tightest = medians
.iter()
.map(|(_, width)| *width)
.min()
.unwrap_or_default();
medians
.into_iter()
.filter(|(_, width)| *width <= tightest * 2)
.map(|(id, _)| id)
.collect()
}
fn median_width(changes: &[Change], id: SourceId) -> Option<std::time::Duration> {
let mut widths: Vec<std::time::Duration> = changes
.iter()
.filter_map(|c| c.containing.iter().find(|(s, _)| *s == id))
.filter_map(|(_, width)| *width)
.collect();
widths.sort();
widths.get(widths.len() / 2).copied()
}
fn on_a_cycle(
candidates: &[&PaneWindow<'_>],
edges: &[(SourceId, SourceId)],
merged: &[Vec<SourceId>],
) -> Vec<SourceId> {
let node = |id: SourceId| -> SourceId {
merged
.iter()
.find(|group| group.contains(&id))
.and_then(|group| group.iter().min().copied())
.unwrap_or(id)
};
let mut implicated: Vec<SourceId> = Vec::new();
for pane in candidates {
let start = node(pane.source);
let mut seen: Vec<SourceId> = Vec::new();
let mut stack: Vec<SourceId> = edges
.iter()
.filter(|(from, _)| node(*from) == start)
.map(|(_, to)| node(*to))
.collect();
let mut cyclic = false;
while let Some(current) = stack.pop() {
if current == start {
cyclic = true;
break;
}
if seen.contains(¤t) {
continue;
}
seen.push(current);
stack.extend(
edges
.iter()
.filter(|(from, _)| node(*from) == current)
.map(|(_, to)| node(*to)),
);
}
if cyclic {
implicated.push(pane.source);
}
}
implicated.sort();
implicated
}
#[cfg(test)]
mod tests {
use std::path::PathBuf;
use std::time::{Duration, Instant};
use super::*;
const D: Duration = Duration::from_millis(250);
#[test]
fn a_fire_becomes_due_when_the_window_closes() {
let t = Instant::now();
let mut g = DebounceGate::new(D);
assert!(!g.due(t)); g.fire(t);
assert!(!g.due(t + Duration::from_millis(100))); assert!(g.due(t + D)); assert!(!g.due(t + D)); }
#[test]
fn fires_inside_the_window_do_not_move_it() {
let t = Instant::now();
let mut g = DebounceGate::new(D);
g.fire(t);
g.fire(t + Duration::from_millis(200));
assert!(g.due(t + D)); }
#[test]
fn a_fire_after_the_window_closed_opens_a_new_one() {
let t = Instant::now();
let mut g = DebounceGate::new(D);
g.fire(t);
assert!(g.due(t + D));
g.fire(t + D * 2);
assert!(!g.due(t + D * 2));
assert!(g.due(t + D * 3));
}
#[test]
fn a_zero_window_is_due_at_the_fire_instant() {
let t = Instant::now();
let mut g = DebounceGate::new(Duration::ZERO);
g.fire(t);
assert!(g.due(t));
assert!(!g.due(t));
}
#[test]
fn sustained_sub_window_fires_never_starve_the_spawn() {
let t = Instant::now();
let mut g = DebounceGate::new(D);
let mut spawns = 0;
for i in 0..20 {
let now = t + Duration::from_millis(50 * i);
g.fire(now);
if g.due(now) {
spawns += 1;
}
}
assert!(spawns >= 3, "starved: {spawns} spawns over 1s at D=250ms");
}
use std::path::Path;
use std::time::SystemTime;
fn touch_at(path: &Path, t: SystemTime) {
std::fs::File::options()
.append(true)
.open(path)
.unwrap()
.set_modified(t)
.unwrap();
}
#[test]
fn the_first_observation_is_a_baseline_not_a_fire() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("state.json");
std::fs::write(&f, b"x").unwrap();
let mut w = MtimeWatch::new(f);
assert!(!w.fired()); assert!(!w.fired()); }
#[test]
fn an_mtime_change_fires_once() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("state.json");
std::fs::write(&f, b"x").unwrap();
let mut w = MtimeWatch::new(f.clone());
w.fired();
touch_at(&f, SystemTime::now() + Duration::from_secs(5));
assert!(w.fired());
assert!(!w.fired());
}
#[test]
fn an_absent_path_is_stable_and_fires_on_appearance() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("not-yet");
let mut w = MtimeWatch::new(f.clone());
assert!(!w.fired()); assert!(!w.fired()); std::fs::write(&f, b"x").unwrap();
assert!(w.fired()); }
#[test]
fn a_directory_fires_on_an_immediate_entrys_edit() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("finding.md");
std::fs::write(&f, b"x").unwrap();
let mut w = MtimeWatch::new(dir.path().to_path_buf());
w.fired();
touch_at(&f, SystemTime::now() + Duration::from_secs(5));
assert!(w.fired());
}
#[test]
fn a_directory_is_not_recursive() {
let dir = tempfile::tempdir().unwrap();
let sub = dir.path().join("sub");
std::fs::create_dir(&sub).unwrap();
let deep = sub.join("deep.md");
std::fs::write(&deep, b"x").unwrap();
let mut w = MtimeWatch::new(dir.path().to_path_buf());
w.fired();
touch_at(&deep, SystemTime::now() + Duration::from_secs(5));
assert!(!w.fired()); }
#[test]
fn a_set_fires_when_any_member_fires() {
let dir = tempfile::tempdir().unwrap();
let a = dir.path().join("a");
let b = dir.path().join("b");
std::fs::write(&a, b"x").unwrap();
std::fs::write(&b, b"x").unwrap();
let mut set = MtimeWatchSet::new(vec![a, b.clone()]);
set.fired();
touch_at(&b, SystemTime::now() + Duration::from_secs(5));
assert!(set.fired());
}
#[test]
fn specs_parse_by_scheme() {
assert_eq!(
parse_trigger("file:/tmp/state.json").unwrap(),
TriggerSpec::File(PathBuf::from("/tmp/state.json"))
);
#[cfg(unix)]
{
assert_eq!(
parse_trigger("fifo:/tmp/rat.trigger").unwrap(),
TriggerSpec::Fifo(PathBuf::from("/tmp/rat.trigger"))
);
assert_eq!(parse_trigger("fd:3").unwrap(), TriggerSpec::Fd(3));
}
}
#[test]
fn a_bare_path_teaches_the_schemes() {
let err = parse_trigger("/tmp/state.json").unwrap_err().to_string();
assert!(err.contains("fifo:"), "{err}");
assert!(err.contains("file:"), "{err}");
assert!(err.contains("fd:"), "{err}");
}
#[test]
fn an_empty_path_after_a_scheme_is_rejected() {
assert!(parse_trigger("file:").is_err());
#[cfg(unix)]
assert!(parse_trigger("fifo:").is_err());
}
#[test]
fn a_non_numeric_fd_is_rejected() {
#[cfg(unix)]
assert!(parse_trigger("fd:three").is_err());
#[cfg(unix)]
assert!(parse_trigger("fd:-1").is_err());
}
#[cfg(unix)]
#[test]
fn an_fd_past_the_select_limit_is_rejected_at_parse() {
let err = parse_trigger("fd:1024").unwrap_err().to_string();
assert!(err.contains("select"), "{err}");
assert!(parse_trigger("fd:1023").is_ok());
}
#[cfg(windows)]
#[test]
fn unix_only_schemes_teach_file_on_windows() {
for spec in ["fifo:/tmp/x", "fd:3"] {
let err = parse_trigger(spec).unwrap_err().to_string();
assert!(err.contains("file:"), "{err}");
}
}
fn observe_alone(ledger: &mut PathLedger, bracket: &Bracket) {
ledger.observe_bracket(bracket, &[]);
}
fn log_with(entries: &[(SourceId, BracketId, Option<Duration>)]) -> WindowLog {
let mut log = WindowLog::new(Duration::from_secs(30));
let t = Instant::now();
for (source, want, width) in entries {
let id = log.open_bracket(*source, t, Vec::new());
assert_eq!(id, *want, "ids are handed out in order");
if let Some(w) = width {
log.close_bracket(id, t + *w, Vec::new());
}
}
log
}
fn ledger_over(paths: &[&Path]) -> PathLedger {
PathLedger::new(paths.iter().map(PathBuf::from).collect())
}
fn mtime_base() -> SystemTime {
SystemTime::UNIX_EPOCH + Duration::from_secs(1_000_000)
}
#[test]
fn a_change_with_no_bracket_over_it_is_exogenous() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
touch_at(&f, mtime_base() + Duration::from_secs(1));
ledger.observe(t, &[]);
assert_eq!(ledger.exogenous(&f), 1);
}
#[test]
fn a_change_inside_a_bracket_is_endogenous() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
touch_at(&f, mtime_base() + Duration::from_secs(1));
let log = log_with(&[(SourceId(0), BracketId(0), Some(Duration::from_millis(7)))]);
ledger.observe(t, &[(SourceId(0), BracketId(0))]);
assert_eq!(ledger.exogenous(&f), 0);
assert_eq!(ledger.changes(&f, &log).len(), 1);
}
#[test]
fn the_first_stat_only_establishes_a_baseline() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
let mut ledger = ledger_over(&[&f]);
ledger.observe(Instant::now(), &[]);
assert_eq!(ledger.exogenous(&f), 0);
}
#[test]
fn an_absent_path_is_stable_and_its_appearance_is_one_change() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("not-yet");
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
ledger.observe(t, &[]); assert_eq!(ledger.exogenous(&f), 0);
std::fs::write(&f, b"here").unwrap();
ledger.observe(t + Duration::from_millis(50), &[]);
assert_eq!(ledger.exogenous(&f), 1);
}
#[test]
fn observe_bracket_credits_the_source_whose_bracket_it_was() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
let open = stamps(std::slice::from_ref(&f));
touch_at(&f, mtime_base() + Duration::from_secs(1));
let close = stamps(std::slice::from_ref(&f));
observe_alone(
&mut ledger,
&Bracket {
id: BracketId(0),
source: SourceId(3),
opened: t,
closed: Some(t + Duration::from_millis(9)),
open_stamps: open,
close_stamps: close,
},
);
assert_eq!(ledger.exogenous(&f), 0);
let log = log_with(&[(SourceId(9), BracketId(0), Some(Duration::from_millis(9)))]);
let c = ledger.changes(&f, &log);
assert_eq!(c.len(), 1);
assert_eq!(
c[0].containing,
vec![(SourceId(3), Some(Duration::from_millis(9)))]
);
}
#[test]
fn overlapping_includes_a_child_that_is_still_running() {
let mut log = WindowLog::new(Duration::from_secs(30));
let t = Instant::now();
let mine = log.open_bracket(SourceId(0), t + Duration::from_millis(10), Vec::new());
let running = log.open_bracket(SourceId(4), t + Duration::from_millis(11), Vec::new());
log.open_bracket(SourceId(5), t + Duration::from_millis(40), Vec::new());
let closed = log
.close_bracket(mine, t + Duration::from_millis(30), Vec::new())
.expect("still live")
.clone();
assert_eq!(
log.overlapping(&closed),
vec![(SourceId(4), running)],
"the child still running is named; the later one is not"
);
assert_eq!(log.width_of(running), None, "and it has no width yet");
}
#[test]
fn a_still_running_child_counts_for_coverage_but_not_for_tightness() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut log = WindowLog::new(Duration::from_secs(30));
let t = Instant::now();
let done = log.open_bracket(SourceId(3), t, Vec::new());
log.close_bracket(done, t + Duration::from_millis(9), Vec::new());
let running = log.open_bracket(SourceId(1), t, Vec::new());
let mut ledger = ledger_over(&[&f]);
let open = stamps(std::slice::from_ref(&f));
touch_at(&f, mtime_base() + Duration::from_secs(1));
let close = stamps(std::slice::from_ref(&f));
ledger.observe_bracket(
&Bracket {
id: done,
source: SourceId(3),
opened: t,
closed: Some(t + Duration::from_millis(9)),
open_stamps: open,
close_stamps: close,
},
&[(SourceId(1), running)],
);
let c = ledger.changes(&f, &log);
assert_eq!(c.len(), 1);
assert_eq!(
c[0].containing,
vec![
(SourceId(3), Some(Duration::from_millis(9))),
(SourceId(1), None),
],
"both cover it; only the finished one has a width"
);
assert_eq!(ledger.exogenous(&f), 0, "and it is not exogenous");
assert_eq!(median_width(&c, SourceId(1)), None);
assert_eq!(
median_width(&c, SourceId(3)),
Some(Duration::from_millis(9))
);
log.close_bracket(running, t + Duration::from_millis(20), Vec::new());
let c = ledger.changes(&f, &log);
assert_eq!(
c[0].containing[1],
(SourceId(1), Some(Duration::from_millis(20)))
);
}
#[test]
fn a_change_is_credited_to_every_bracket_that_could_have_contained_it() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
let open = stamps(std::slice::from_ref(&f));
touch_at(&f, mtime_base() + Duration::from_secs(1));
let close = stamps(std::slice::from_ref(&f));
ledger.observe_bracket(
&Bracket {
id: BracketId(0),
source: SourceId(3),
opened: t,
closed: Some(t + Duration::from_millis(9)),
open_stamps: open,
close_stamps: close,
},
&[(SourceId(1), BracketId(1))],
);
let log = log_with(&[
(SourceId(3), BracketId(0), Some(Duration::from_millis(9))),
(SourceId(1), BracketId(1), Some(Duration::from_millis(7))),
]);
let c = ledger.changes(&f, &log);
assert_eq!(c.len(), 1);
assert_eq!(
c[0].containing,
vec![
(SourceId(3), Some(Duration::from_millis(9))),
(SourceId(1), Some(Duration::from_millis(7))),
],
"the observing bracket first, then whoever else was running"
);
assert_eq!(ledger.exogenous(&f), 0, "still not exogenous");
}
#[test]
fn overlapping_reports_the_other_closed_brackets_that_ran_over_this_one() {
let mut log = WindowLog::new(Duration::from_secs(30));
let t = Instant::now();
let mine = log.open_bracket(SourceId(0), t + Duration::from_millis(10), Vec::new());
let left = log.open_bracket(SourceId(1), t, Vec::new());
log.close_bracket(left, t + Duration::from_millis(10), Vec::new());
let inside = log.open_bracket(SourceId(2), t + Duration::from_millis(12), Vec::new());
log.close_bracket(inside, t + Duration::from_millis(14), Vec::new());
let after = log.open_bracket(SourceId(3), t + Duration::from_millis(40), Vec::new());
log.close_bracket(after, t + Duration::from_millis(50), Vec::new());
let running = log.open_bracket(SourceId(4), t + Duration::from_millis(11), Vec::new());
let closed = log
.close_bracket(mine, t + Duration::from_millis(30), Vec::new())
.expect("still live")
.clone();
assert_eq!(
log.overlapping(&closed),
vec![
(SourceId(1), left),
(SourceId(2), inside),
(SourceId(4), running),
],
"never itself and never one that did not overlap — but a child \
still running is exactly the one most likely to be the writer"
);
assert_eq!(log.width_of(inside), Some(Duration::from_millis(2)));
assert_eq!(log.width_of(running), None, "no final width yet");
}
#[test]
fn a_bracket_that_moved_nothing_records_no_change() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
let snap = stamps(std::slice::from_ref(&f));
observe_alone(
&mut ledger,
&Bracket {
id: BracketId(0),
source: SourceId(0),
opened: t,
closed: Some(t + Duration::from_millis(5)),
open_stamps: snap.clone(),
close_stamps: snap,
},
);
assert!(ledger.changes(&f, &log_with(&[])).is_empty());
}
#[test]
fn a_bracket_advances_the_baseline_so_one_change_is_not_counted_twice() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
let open = stamps(std::slice::from_ref(&f));
touch_at(&f, mtime_base() + Duration::from_secs(1));
let close = stamps(std::slice::from_ref(&f));
observe_alone(
&mut ledger,
&Bracket {
id: BracketId(0),
source: SourceId(0),
opened: t,
closed: Some(t + Duration::from_millis(5)),
open_stamps: open,
close_stamps: close,
},
);
let log = log_with(&[(SourceId(0), BracketId(0), Some(Duration::from_millis(5)))]);
assert_eq!(ledger.changes(&f, &log).len(), 1);
ledger.observe(t + Duration::from_millis(60), &[]);
assert_eq!(
ledger.changes(&f, &log).len(),
1,
"the same change must not be counted twice"
);
}
#[test]
fn eviction_drops_changes_older_than_the_window() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
touch_at(&f, mtime_base() + Duration::from_secs(1));
ledger.observe(t, &[]);
assert_eq!(ledger.exogenous(&f), 1);
ledger.evict(t + Duration::from_secs(31), Duration::from_secs(30));
assert_eq!(ledger.exogenous(&f), 0, "the window must mean NOW");
}
#[test]
fn the_ledger_never_swallows_a_trigger_set_fire() {
let dir = tempfile::tempdir().unwrap();
let f = dir.path().join("sa");
std::fs::write(&f, b"0").unwrap();
touch_at(&f, mtime_base());
let mut set = MtimeWatchSet::new(vec![f.clone()]);
assert!(!set.fired(), "baseline");
let mut ledger = ledger_over(&[&f]);
let t = Instant::now();
touch_at(&f, mtime_base() + Duration::from_secs(1));
ledger.observe(t, &[]);
ledger.observe(t + Duration::from_millis(50), &[]);
assert!(set.fired(), "the trigger must still see its own change");
}
const W: Duration = Duration::from_secs(30);
fn secs(n: u64) -> Duration {
Duration::from_secs(n)
}
#[test]
fn a_windowed_respawn_count_falls_as_evidence_expires() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
for i in 0..50 {
log.record_respawn(SourceId(0), t0 + Duration::from_millis(i * 10));
}
assert_eq!(log.respawns_in_window(SourceId(0), t0 + secs(1)), 50);
assert_eq!(log.respawns_in_window(SourceId(0), t0 + secs(40)), 0);
}
#[test]
fn respawns_are_counted_per_source() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
log.record_respawn(SourceId(0), t0);
log.record_respawn(SourceId(1), t0);
log.record_respawn(SourceId(1), t0);
assert_eq!(log.respawns_in_window(SourceId(0), t0 + secs(1)), 1);
assert_eq!(log.respawns_in_window(SourceId(1), t0 + secs(1)), 2);
}
#[test]
fn busy_fraction_unions_overlapping_brackets_rather_than_summing() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let a = log.open_bracket(SourceId(0), t0, Vec::new());
let b = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(a, t0 + secs(1), Vec::new());
log.close_bracket(b, t0 + secs(1), Vec::new());
let f = log.busy_fraction(t0 + secs(10));
assert!(
(f - 0.1).abs() < 0.01,
"two overlapping 1s brackets in 10s is 10%, not 20% — got {f}"
);
}
#[test]
fn busy_fraction_sums_disjoint_brackets() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let a = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(a, t0 + secs(1), Vec::new());
let b = log.open_bracket(SourceId(1), t0 + secs(5), Vec::new());
log.close_bracket(b, t0 + secs(6), Vec::new());
let f = log.busy_fraction(t0 + secs(10));
assert!(
(f - 0.2).abs() < 0.01,
"two disjoint 1s brackets in 10s is 20% — got {f}"
);
}
#[test]
fn an_open_bracket_counts_as_busy_up_to_now() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
log.open_bracket(SourceId(0), t0 + secs(9), Vec::new());
let f = log.busy_fraction(t0 + secs(10));
assert!(
(f - 0.1).abs() < 0.01,
"a still-open 1s bracket is 10% — got {f}"
);
}
#[test]
fn close_bracket_returns_the_completed_record() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
let id = log.open_bracket(SourceId(2), t0, Vec::new());
let closed = log.close_bracket(id, t0 + Duration::from_millis(7), Vec::new());
let closed = closed.expect("a live id must close");
assert_eq!(closed.source, SourceId(2));
assert_eq!(closed.width(), Some(Duration::from_millis(7)));
}
#[test]
fn an_evicted_bracket_never_shifts_a_live_bracket_id() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let old = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(old, t0 + secs(1), Vec::new());
let live = log.open_bracket(SourceId(7), t0 + secs(9), Vec::new());
log.evict(t0 + secs(20));
let closed = log
.close_bracket(live, t0 + secs(20), Vec::new())
.expect("the live bracket must still be closeable");
assert_eq!(closed.source, SourceId(7), "closed the wrong record");
}
#[test]
fn closing_an_evicted_id_is_a_no_op_returning_none() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + secs(1), Vec::new());
log.evict(t0 + secs(30));
assert!(log.close_bracket(id, t0 + secs(30), Vec::new()).is_none());
}
#[test]
fn covering_reports_closed_brackets_with_final_widths() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
let id = log.open_bracket(SourceId(4), t0, Vec::new());
log.close_bracket(id, t0 + Duration::from_millis(20), Vec::new());
let over = log.covering(t0 + Duration::from_millis(10));
assert_eq!(over, vec![(SourceId(4), Duration::from_millis(20))]);
assert!(log.covering(t0 + secs(5)).is_empty(), "outside the bracket");
}
#[test]
fn covering_withholds_an_open_bracket_and_any_open_reports_it() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
log.open_bracket(SourceId(0), t0, Vec::new());
assert!(log.covering(t0 + Duration::from_millis(5)).is_empty());
assert!(log.any_open(t0 + Duration::from_millis(5)));
}
#[test]
fn an_arrival_with_nothing_in_flight_is_exogenous_immediately() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
log.observe_arrival(
TriggerKey("fifo:/tmp/a".into()),
Observation {
empty_since: Some(t0),
observed_at: t0 + Duration::from_millis(1),
},
);
let key = TriggerKey("fifo:/tmp/a".into());
let arrivals = log.arrivals(&key);
assert_eq!(arrivals.len(), 1);
assert!(log.classify(&arrivals[0].observation).is_disjoint());
}
#[test]
fn an_arrival_resolves_its_coverage_on_read_and_its_widths_with_it() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.observe_arrival(
TriggerKey("fifo:/tmp/a".into()),
Observation {
empty_since: Some(t0 + Duration::from_millis(1)),
observed_at: t0 + Duration::from_millis(3),
},
);
let key = TriggerKey("fifo:/tmp/a".into());
{
let arrivals = log.arrivals(&key);
assert_eq!(
log.classify(&arrivals[0].observation),
TemporalCoverage::Covered(vec![(SourceId(1), None)]),
"covered by the open bracket, with no width claimed yet"
);
}
log.close_bracket(id, t0 + Duration::from_millis(40), Vec::new());
let arrivals = log.arrivals(&key);
assert_eq!(
log.classify(&arrivals[0].observation),
TemporalCoverage::Covered(vec![(SourceId(1), Some(Duration::from_millis(40)))]),
"the FINAL width, not the 3ms that had elapsed when it was read"
);
}
#[test]
fn two_triggers_on_one_pane_are_kept_separate_not_merged() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
log.observe_arrival(TriggerKey("fifo:/tmp/a".into()), at(t0));
log.observe_arrival(TriggerKey("fifo:/tmp/b".into()), at(t0));
log.observe_arrival(TriggerKey("fifo:/tmp/b".into()), at(t0));
assert_eq!(log.arrivals(&TriggerKey("fifo:/tmp/a".into())).len(), 1);
assert_eq!(log.arrivals(&TriggerKey("fifo:/tmp/b".into())).len(), 2);
}
#[test]
fn an_overflow_forces_abstention_for_any_window_it_touches() {
let mut log = WindowLog::new(W);
let t0 = Instant::now();
log.record_overflow(t0);
assert!(log.evidence_lost(t0 + secs(1)));
assert!(
!log.evidence_lost(t0 + secs(40)),
"and it expires with the window"
);
}
#[test]
fn eviction_drops_brackets_respawns_arrivals_and_overflows_alike() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + Duration::from_millis(5), Vec::new());
log.record_respawn(SourceId(0), t0);
log.observe_arrival(TriggerKey("fifo:/tmp/a".into()), at(t0));
log.record_overflow(t0);
log.evict(t0 + secs(30));
assert_eq!(log.respawns_in_window(SourceId(0), t0 + secs(30)), 0);
assert!(log.arrivals(&TriggerKey("fifo:/tmp/a".into())).is_empty());
assert!(!log.evidence_lost(t0 + secs(30)));
assert!((log.busy_fraction(t0 + secs(30)) - 0.0).abs() < 1e-9);
}
#[test]
fn the_gap_to_the_nearest_bracket_is_signed_by_which_side_it_missed() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(3), t0, Vec::new());
log.close_bracket(id, t0 + Duration::from_millis(10), Vec::new());
let (source, ms) = log
.nearest_bracket_gap(t0 + Duration::from_millis(12))
.expect("a bracket to measure against");
assert_eq!(source, SourceId(3));
assert!((ms - 2.0).abs() < 0.5, "late must read positive, got {ms}");
let (_, ms) = log
.nearest_bracket_gap(t0 - Duration::from_millis(4))
.expect("a bracket to measure against");
assert!((ms + 4.0).abs() < 0.5, "early must read negative, got {ms}");
assert!(WindowLog::new(secs(10)).nearest_bracket_gap(t0).is_none());
}
#[test]
fn eviction_keeps_a_bracket_that_still_overlaps_the_window() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + secs(6), Vec::new());
log.evict(t0 + secs(11));
let f = log.busy_fraction(t0 + secs(11));
assert!(
f > 0.0,
"a bracket overlapping the window must survive — got {f}"
);
}
#[test]
fn eviction_retains_a_bracket_a_live_arrival_still_references() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + Duration::from_millis(5), Vec::new());
log.observe_arrival(
TriggerKey("fifo:/tmp/a".into()),
at(t0 + Duration::from_millis(1)),
);
log.evict(t0 + Duration::from_millis(500));
let key = TriggerKey("fifo:/tmp/a".into());
let arrivals = log.arrivals(&key);
assert_eq!(arrivals.len(), 1);
assert_eq!(
log.classify(&arrivals[0].observation),
TemporalCoverage::Covered(vec![(SourceId(0), Some(Duration::from_millis(5)))]),
"the reached bracket must have been retained"
);
}
fn ms(n: u64) -> Duration {
Duration::from_millis(n)
}
fn changes_all(n: usize, containing: &[(SourceId, Duration)]) -> Vec<Change> {
let resolved: Vec<(SourceId, Option<Duration>)> =
containing.iter().map(|(s, w)| (*s, Some(*w))).collect();
(0..n)
.map(|_| Change {
containing: resolved.clone(),
})
.collect()
}
#[test]
fn credit_merges_two_panes_whose_children_cost_the_same() {
let credited = credit(&changes_all(
10,
&[(SourceId(0), ms(22)), (SourceId(1), ms(24))],
));
assert_eq!(credited, vec![SourceId(0), SourceId(1)]);
}
#[test]
fn credit_rejects_a_producer_whose_bracket_merely_contains_the_consumers() {
let credited = credit(&changes_all(
10,
&[(SourceId(0), ms(168)), (SourceId(1), ms(6))],
));
assert_eq!(credited, vec![SourceId(1)], "only the tight one");
}
#[test]
fn credit_requires_more_than_half_the_changes_not_merely_some() {
let mut changes = changes_all(8, &[(SourceId(1), ms(5))]);
changes.extend(changes_all(
2,
&[(SourceId(1), ms(5)), (SourceId(9), ms(1))],
));
let credited = credit(&changes);
assert_eq!(
credited,
vec![SourceId(1)],
"SourceId(9) covered 2 of 10 and must not be credited despite being tighter"
);
}
#[test]
fn credit_of_nothing_is_nothing() {
assert!(credit(&[]).is_empty());
assert!(credit(&changes_all(3, &[])).is_empty());
}
fn pane<'a>(
id: usize,
watched: &'a [std::path::PathBuf],
readers: &'a [TriggerKey],
) -> PaneWindow<'a> {
PaneWindow {
source: SourceId(id),
trigger_respawns: 50,
watched,
readers,
}
}
fn ledger_with(log: &mut WindowLog, entries: &[(&std::path::Path, Vec<Change>)]) -> PathLedger {
let mut ledger = PathLedger::new(Vec::new());
let t = Instant::now();
let mut ids: std::collections::HashMap<(usize, Option<Duration>), BracketId> =
std::collections::HashMap::new();
for (path, changes) in entries {
for change in changes {
let containing: Vec<(SourceId, BracketId)> = change
.containing
.iter()
.map(|(source, width)| {
let id = *ids.entry((source.0, *width)).or_insert_with(|| {
let id = log.open_bracket(*source, t, Vec::new());
if let Some(w) = width {
log.close_bracket(id, t + *w, Vec::new());
}
id
});
(*source, id)
})
.collect();
ledger.inject(path, t, containing);
}
}
ledger
}
#[test]
fn a_two_pane_cycle_trips_and_names_both() {
let a = std::path::PathBuf::from("/sa");
let b = std::path::PathBuf::from("/sb");
let both = [(SourceId(0), ms(22)), (SourceId(1), ms(24))];
let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(
&mut log,
&[(&a, changes_all(10, &both)), (&b, changes_all(10, &both))],
);
let (wa, wb) = (vec![a.clone()], vec![b.clone()]);
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, &wa, &none), pane(1, &wb, &none)];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert_eq!(v.panes, vec![SourceId(0), SourceId(1)]);
assert!(!v.abstained);
}
#[test]
fn concurrent_children_are_never_ordered() {
let a = std::path::PathBuf::from("/sa");
let both = [(SourceId(0), ms(22)), (SourceId(1), ms(24))];
let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(&mut log, &[(&a, changes_all(10, &both))]);
let wa = vec![a.clone()];
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, &wa, &none), pane(1, &wa, &none)];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert!(v.ordered.is_none(), "a merged pair cannot be ordered");
}
#[test]
fn a_one_way_producer_consumer_pair_does_not_trip() {
let data = std::path::PathBuf::from("/data");
let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(
&mut log,
&[(&data, changes_all(10, &[(SourceId(0), ms(6))]))],
);
let watched1 = vec![data.clone()];
let watched0: Vec<std::path::PathBuf> = vec![std::path::PathBuf::from("/upstream")];
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, &watched0, &none), pane(1, &watched1, &none)];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert!(
v.panes.is_empty(),
"an acyclic one-way chain must never be implicated"
);
}
#[test]
fn an_expensive_producer_chain_does_not_trip_end_to_end() {
let d1 = std::path::PathBuf::from("/d1"); let d2 = std::path::PathBuf::from("/d2"); let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(
&mut log,
&[
(&d1, changes_all(10, &[(SourceId(0), ms(168))])),
(
&d2,
changes_all(10, &[(SourceId(0), ms(168)), (SourceId(1), ms(6))]),
),
],
);
let (wa, wb, wc) = (
vec![std::path::PathBuf::from("/upstream")],
vec![d1.clone()],
vec![d2.clone()],
);
let none: Vec<TriggerKey> = Vec::new();
let panes = [
pane(0, &wa, &none),
pane(1, &wb, &none),
pane(2, &wc, &none),
];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert!(
v.panes.is_empty(),
"an acyclic chain must not trip because one bracket contains another: {:?}",
v.panes
);
}
#[test]
fn too_few_trigger_driven_respawns_never_trips() {
let a = std::path::PathBuf::from("/sa");
let both = [(SourceId(0), ms(22)), (SourceId(1), ms(24))];
let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(&mut log, &[(&a, changes_all(10, &both))]);
let wa = vec![a.clone()];
let none: Vec<TriggerKey> = Vec::new();
let mut slow = pane(0, &wa, &none);
slow.trigger_respawns = 3;
let panes = [slow];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert!(v.panes.is_empty());
}
#[test]
fn one_exogenous_observation_clears_the_veto() {
let a = std::path::PathBuf::from("/sa");
let both = [(SourceId(0), ms(22)), (SourceId(1), ms(24))];
let mut changes = changes_all(10, &both);
changes.push(Change {
containing: Vec::new(), });
let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(&mut log, &[(&a, changes)]);
let wa = vec![a.clone()];
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, &wa, &none), pane(1, &wa, &none)];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert!(v.panes.is_empty(), "one exogenous change is enough");
}
#[test]
fn a_pane_watching_nothing_is_never_implicated() {
let ledger = PathLedger::new(Vec::new());
let log = WindowLog::new(secs(30));
let nothing: Vec<std::path::PathBuf> = Vec::new();
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, ¬hing, &none)];
let v = LoopSuspicion::default().evaluate(Instant::now(), &ledger, &log, &panes);
assert!(v.panes.is_empty());
}
#[test]
fn a_busy_dashboard_abstains_rather_than_guessing() {
let a = std::path::PathBuf::from("/sa");
let both = [(SourceId(0), ms(22)), (SourceId(1), ms(24))];
let mut log = WindowLog::new(secs(10));
let ledger = ledger_with(&mut log, &[(&a, changes_all(10, &both))]);
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + secs(9), Vec::new());
let wa = vec![a.clone()];
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, &wa, &none), pane(1, &wa, &none)];
let v = LoopSuspicion::default().evaluate(t0 + secs(10), &ledger, &log, &panes);
assert!(v.abstained, "90% duty must abstain");
assert!(v.panes.is_empty(), "abstaining accuses nobody");
}
#[test]
fn lost_reader_evidence_forces_abstention() {
let a = std::path::PathBuf::from("/sa");
let both = [(SourceId(0), ms(22)), (SourceId(1), ms(24))];
let mut log = WindowLog::new(secs(30));
let ledger = ledger_with(&mut log, &[(&a, changes_all(10, &both))]);
let t0 = Instant::now();
log.record_overflow(t0);
let wa = vec![a.clone()];
let none: Vec<TriggerKey> = Vec::new();
let panes = [pane(0, &wa, &none), pane(1, &wa, &none)];
let v = LoopSuspicion::default().evaluate(t0 + secs(1), &ledger, &log, &panes);
assert!(v.abstained);
}
#[test]
fn an_arrival_with_an_unresolved_width_is_deferred_from_credit() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let key = TriggerKey("fifo:/tmp/a".into());
log.open_bracket(SourceId(0), t0, Vec::new()); log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(1)),
observed_at: t0 + ms(3),
},
);
let changes = LoopSuspicion::arrival_changes(&log, &key);
assert_eq!(changes.len(), 1);
assert_eq!(
changes[0].containing,
vec![(SourceId(0), None)],
"covered, with no width claimed yet"
);
assert!(
credit(&changes).is_empty(),
"an unresolved width defers the credit"
);
}
fn obs(from: Instant, to: Instant) -> Observation {
Observation {
empty_since: Some(from),
observed_at: to,
}
}
#[test]
fn an_interval_inside_one_bracket_is_that_source_running() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(2), t0, Vec::new());
log.close_bracket(id, t0 + ms(10), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(2), t0 + ms(8))),
TemporalCoverage::Covered(vec![(SourceId(2), Some(ms(10)))])
);
}
#[test]
fn an_interval_touching_no_bracket_at_all_is_disjoint() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(6), t0 + ms(9))),
TemporalCoverage::Disjoint
);
}
#[test]
fn an_interval_that_straddles_a_bracket_edge_proves_nothing() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(3), t0 + ms(7))),
TemporalCoverage::Ambiguous
);
}
#[test]
fn an_interval_with_no_lower_bound_proves_nothing() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + ms(10), Vec::new());
let unbounded = Observation {
empty_since: None,
observed_at: t0 + ms(5),
};
assert_eq!(log.classify(&unbounded), TemporalCoverage::Ambiguous);
}
#[test]
fn union_coverage_reports_every_contributor_with_its_own_width() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let a = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(a, t0 + ms(5), Vec::new());
let b = log.open_bracket(SourceId(1), t0 + ms(4), Vec::new());
log.close_bracket(b, t0 + ms(9), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(1), t0 + ms(8))),
TemporalCoverage::Covered(
vec![(SourceId(0), Some(ms(5))), (SourceId(1), Some(ms(5))),]
)
);
}
#[test]
fn a_gap_between_two_brackets_makes_the_span_ambiguous() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let a = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(a, t0 + ms(3), Vec::new());
let b = log.open_bracket(SourceId(1), t0 + ms(6), Vec::new());
log.close_bracket(b, t0 + ms(9), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(1), t0 + ms(8))),
TemporalCoverage::Ambiguous
);
}
#[test]
fn a_still_open_bracket_covers_from_its_start_and_reports_no_width() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
log.open_bracket(SourceId(4), t0, Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(1), t0 + ms(50))),
TemporalCoverage::Covered(vec![(SourceId(4), None)])
);
}
fn at(t: Instant) -> Observation {
Observation {
empty_since: Some(t),
observed_at: t,
}
}
fn us(n: u64) -> Duration {
Duration::from_micros(n)
}
fn empty_ledger() -> PathLedger {
PathLedger::new(Vec::new())
}
#[test]
fn an_observation_that_merely_straddles_a_close_does_not_veto() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(3)),
observed_at: t0 + ms(5) + us(200),
},
);
let pane = PaneWindow {
source: SourceId(0),
trigger_respawns: 100,
watched: &[],
readers: std::slice::from_ref(&key),
};
assert!(
LoopSuspicion::default().closed_everywhere(&empty_ledger(), &log, &pane),
"an ambiguous observation must not read as an outside writer"
);
}
#[test]
fn an_observation_wholly_outside_every_bracket_still_vetoes() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(6)),
observed_at: t0 + ms(9),
},
);
let pane = PaneWindow {
source: SourceId(0),
trigger_respawns: 100,
watched: &[],
readers: std::slice::from_ref(&key),
};
assert!(
!LoopSuspicion::default().closed_everywhere(&empty_ledger(), &log, &pane),
"a definitely-exogenous observation must still veto"
);
}
#[test]
fn only_a_covered_interval_produces_an_edge() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(10), Vec::new());
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(2)),
observed_at: t0 + ms(8),
},
);
assert_eq!(
credit(&LoopSuspicion::arrival_changes(&log, &key)),
vec![SourceId(1)]
);
}
#[test]
fn an_ambiguous_interval_contributes_no_edge_at_all() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(3)),
observed_at: t0 + ms(7),
},
);
let changes = LoopSuspicion::arrival_changes(&log, &key);
assert_eq!(changes.len(), 1, "it is still an observation");
assert!(changes[0].containing.is_empty(), "and it covers no source");
assert!(credit(&changes).is_empty());
}
#[test]
fn a_zero_width_interval_inside_a_running_child_is_covered_not_disjoint() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
log.open_bracket(SourceId(1), t0, Vec::new()); let t = t0 + ms(3);
assert_eq!(
log.classify(&Observation {
empty_since: Some(t),
observed_at: t,
}),
TemporalCoverage::Covered(vec![(SourceId(1), None)])
);
}
#[test]
fn a_bracket_closing_exactly_at_the_read_does_not_prove_coverage() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(8), Vec::new());
assert_eq!(
log.classify(&Observation {
empty_since: Some(t0 + ms(2)),
observed_at: t0 + ms(8), }),
TemporalCoverage::Ambiguous
);
assert_eq!(
log.classify(&Observation {
empty_since: Some(t0 + ms(2)),
observed_at: t0 + ms(8) - Duration::from_nanos(1),
}),
TemporalCoverage::Covered(vec![(SourceId(1), Some(ms(8)))])
);
}
#[test]
fn an_interval_that_only_touches_a_bracket_edge_is_ambiguous_not_disjoint() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
let closed_at = t0 + ms(5);
log.close_bracket(id, closed_at, Vec::new());
assert_eq!(
log.classify(&Observation {
empty_since: Some(closed_at),
observed_at: closed_at,
}),
TemporalCoverage::Ambiguous
);
}
#[test]
fn a_zero_width_interval_at_the_instant_a_bracket_opens_is_covered() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
log.open_bracket(SourceId(2), t0, Vec::new());
assert_eq!(
log.classify(&Observation {
empty_since: Some(t0),
observed_at: t0,
}),
TemporalCoverage::Covered(vec![(SourceId(2), None)])
);
}
#[test]
fn ambiguous_arrivals_still_count_against_a_sources_dominance() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let key = TriggerKey("fifo:/tmp/a".into());
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(10), Vec::new());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(2)),
observed_at: t0 + ms(8),
},
);
for n in 0..9 {
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(9)),
observed_at: t0 + ms(11 + n),
},
);
}
let changes = LoopSuspicion::arrival_changes(&log, &key);
assert_eq!(changes.len(), 10, "all ten arrivals are in the denominator");
assert!(
credit(&changes).is_empty(),
"1 of 10 is not dominance, and must not be credited"
);
}
#[test]
fn eviction_retains_a_bracket_a_live_interval_still_reaches() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
log.observe_arrival(
TriggerKey("fifo:/tmp/a".into()),
Observation {
empty_since: Some(t0 + ms(1)),
observed_at: t0 + ms(4),
},
);
log.evict(t0 + ms(500));
assert_eq!(log.bracket_count(), 1);
}
#[test]
fn a_pane_whose_reader_evidence_is_all_ambiguous_abstains() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(5), Vec::new());
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(3)),
observed_at: t0 + ms(7),
},
);
for _ in 0..60 {
log.record_respawn(SourceId(0), t0);
}
let panes = [PaneWindow {
source: SourceId(0),
trigger_respawns: 60,
watched: &[],
readers: std::slice::from_ref(&key),
}];
let v = LoopSuspicion::default().evaluate(t0 + ms(8), &empty_ledger(), &log, &panes);
assert!(v.abstained, "an undecidable graph must say so");
assert!(v.panes.is_empty(), "abstaining accuses nobody");
}
#[test]
fn ambiguity_that_does_not_decide_anything_does_not_abstain() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(10), Vec::new());
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: Some(t0 + ms(2)),
observed_at: t0 + ms(8),
},
);
log.observe_arrival(
key.clone(),
Observation {
empty_since: None,
observed_at: t0 + ms(9),
},
);
for _ in 0..60 {
log.record_respawn(SourceId(0), t0);
}
let panes = [PaneWindow {
source: SourceId(0),
trigger_respawns: 60,
watched: &[],
readers: std::slice::from_ref(&key),
}];
let v = LoopSuspicion::default().evaluate(t0 + ms(11), &empty_ledger(), &log, &panes);
assert!(!v.abstained, "usable evidence exists; the answer stands");
}
#[test]
fn a_proven_loop_is_not_suppressed_by_ambiguity_elsewhere() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let a = log.open_bracket(SourceId(0), t0, Vec::new());
log.close_bracket(a, t0 + ms(10), Vec::new());
let b = log.open_bracket(SourceId(1), t0 + ms(12), Vec::new());
log.close_bracket(b, t0 + ms(22), Vec::new());
let watched_by_1 = TriggerKey("fifo:/tmp/one".into());
log.observe_arrival(
watched_by_1.clone(),
Observation {
empty_since: Some(t0 + ms(2)),
observed_at: t0 + ms(8),
},
);
let watched_by_0 = TriggerKey("fifo:/tmp/zero".into());
log.observe_arrival(
watched_by_0.clone(),
Observation {
empty_since: Some(t0 + ms(14)),
observed_at: t0 + ms(20),
},
);
let muddy = TriggerKey("fifo:/tmp/muddy".into());
log.observe_arrival(
muddy.clone(),
Observation {
empty_since: None,
observed_at: t0 + ms(21),
},
);
for _ in 0..60 {
log.record_respawn(SourceId(0), t0);
log.record_respawn(SourceId(1), t0);
log.record_respawn(SourceId(2), t0);
}
let panes = [
PaneWindow {
source: SourceId(0),
trigger_respawns: 60,
watched: &[],
readers: std::slice::from_ref(&watched_by_0),
},
PaneWindow {
source: SourceId(1),
trigger_respawns: 60,
watched: &[],
readers: std::slice::from_ref(&watched_by_1),
},
PaneWindow {
source: SourceId(2),
trigger_respawns: 60,
watched: &[],
readers: std::slice::from_ref(&muddy),
},
];
let v = LoopSuspicion::default().evaluate(t0 + ms(23), &empty_ledger(), &log, &panes);
assert!(
!v.panes.is_empty(),
"the proven loop must still be reported"
);
assert!(!v.abstained, "a proven loop is an answer");
}
#[test]
fn a_pane_that_is_not_a_candidate_cannot_force_abstention() {
let mut log = WindowLog::new(secs(30));
let t0 = Instant::now();
let key = TriggerKey("fifo:/tmp/a".into());
log.observe_arrival(
key.clone(),
Observation {
empty_since: None,
observed_at: t0 + ms(1),
},
);
let panes = [PaneWindow {
source: SourceId(0),
trigger_respawns: 1, watched: &[],
readers: std::slice::from_ref(&key),
}];
let v = LoopSuspicion::default().evaluate(t0 + ms(2), &empty_ledger(), &log, &panes);
assert!(!v.abstained);
}
#[test]
fn covered_is_temporal_evidence_not_writer_identity() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let id = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(id, t0 + ms(10), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(2), t0 + ms(8))),
TemporalCoverage::Covered(vec![(SourceId(1), Some(ms(10)))])
);
}
#[test]
fn a_descendants_write_is_attributed_to_whoever_happened_to_be_running() {
let mut log = WindowLog::new(secs(10));
let t0 = Instant::now();
let parent = log.open_bracket(SourceId(1), t0, Vec::new());
log.close_bracket(parent, t0 + ms(5), Vec::new());
let bystander = log.open_bracket(SourceId(2), t0 + ms(5), Vec::new());
log.close_bracket(bystander, t0 + ms(12), Vec::new());
assert_eq!(
log.classify(&obs(t0 + ms(6), t0 + ms(9))),
TemporalCoverage::Covered(vec![(SourceId(2), Some(ms(7)))])
);
}
}
#[cfg(test)]
mod matrix {
use super::*;
const W: std::time::Duration = std::time::Duration::from_secs(30);
const BASE: std::time::Duration = std::time::Duration::from_millis(2);
const SLICE: std::time::Duration = std::time::Duration::from_millis(50);
const CHANGES: usize = 7;
const MIN_RESPAWNS: usize = 6;
const RATIOS: [u32; 3] = [1, 5, 25];
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Close {
Worker,
Drain,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Phase {
Locked,
Dephased,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Production {
Synthetic,
Driven,
}
#[derive(Clone, Debug)]
struct Shape {
n: usize,
edges: Vec<(usize, usize)>,
}
impl Shape {
fn has_cycle(&self) -> bool {
(0..self.n).any(|start| {
let mut seen = vec![false; self.n];
let mut stack = vec![start];
let mut first = true;
while let Some(cur) = stack.pop() {
if cur == start && !first {
return true;
}
first = false;
if seen[cur] {
continue;
}
seen[cur] = true;
stack.extend(
self.edges
.iter()
.filter(|(from, _)| *from == cur)
.map(|(_, to)| *to),
);
}
false
})
}
fn canonical(&self) -> Vec<(usize, usize)> {
permutations(self.n)
.into_iter()
.map(|perm| {
let mut mapped: Vec<(usize, usize)> = self
.edges
.iter()
.map(|(a, b)| (perm[*a], perm[*b]))
.collect();
mapped.sort();
mapped
})
.min()
.unwrap_or_default()
}
}
fn permutations(n: usize) -> Vec<Vec<usize>> {
let mut out = vec![Vec::new()];
for _ in 0..n {
let mut next = Vec::new();
for partial in &out {
for v in 0..n {
if !partial.contains(&v) {
let mut p = partial.clone();
p.push(v);
next.push(p);
}
}
}
out = next;
}
out
}
fn shapes(n: usize) -> Vec<Shape> {
let slots: Vec<(usize, usize)> = (0..n).flat_map(|a| (0..n).map(move |b| (a, b))).collect();
let mut seen: Vec<Vec<(usize, usize)>> = Vec::new();
let mut out = Vec::new();
for mask in 0..(1u32 << slots.len()) {
let edges: Vec<(usize, usize)> = slots
.iter()
.enumerate()
.filter(|(i, _)| mask & (1 << i) != 0)
.map(|(_, e)| *e)
.collect();
let shape = Shape { n, edges };
let key = shape.canonical();
if !seen.contains(&key) {
seen.push(key);
out.push(shape);
}
}
out
}
fn named() -> Vec<(&'static str, Shape)> {
vec![
(
"4-cycle",
Shape {
n: 4,
edges: vec![(0, 1), (1, 2), (2, 3), (3, 0)],
},
),
(
"diamond",
Shape {
n: 4,
edges: vec![(0, 1), (0, 2), (1, 3), (2, 3)],
},
),
(
"4-chain",
Shape {
n: 4,
edges: vec![(0, 1), (1, 2), (2, 3)],
},
),
(
"3-cycle beside an unrelated producer-consumer pair",
Shape {
n: 5,
edges: vec![(0, 1), (1, 2), (2, 0), (3, 4)],
},
),
]
}
fn width_of(pane: usize, ratio: u32) -> std::time::Duration {
if pane == 0 { BASE } else { BASE * ratio }
}
fn touch(path: &std::path::Path, seq: u64) {
let f = std::fs::File::options().write(true).open(path).unwrap();
let when = std::time::SystemTime::UNIX_EPOCH + std::time::Duration::from_secs(seq);
f.set_times(std::fs::FileTimes::new().set_modified(when))
.unwrap();
}
struct Case {
shape: Shape,
ratio: u32,
close: Close,
phase: Phase,
production: Production,
}
fn evaluate_case(dir: &std::path::Path, case: &Case, seq: &mut u64) -> Verdict {
let n = case.shape.n;
let paths: Vec<std::path::PathBuf> = case
.shape
.edges
.iter()
.map(|(a, b)| dir.join(format!("p{a}_{b}")))
.collect();
for path in &paths {
std::fs::write(path, b"0").unwrap();
*seq += 1;
touch(path, *seq);
}
let mut ledger = PathLedger::new(paths.clone());
let mut log = WindowLog::new(W);
let t0 = std::time::Instant::now();
let close_slop = if case.close == Close::Drain {
SLICE
} else {
std::time::Duration::ZERO
};
let widest = (0..n)
.map(|pane| width_of(pane, case.ratio))
.max()
.unwrap_or(BASE);
let spread = widest + close_slop + std::time::Duration::from_millis(20);
let step = spread * (n as u32 + 1);
for c in 0..CHANGES {
let round = t0 + step * (c as u32);
for pane in 0..n {
log.record_respawn(SourceId(pane), round);
}
let open_at = |pane: usize| match case.phase {
Phase::Locked => round,
Phase::Dephased => round + spread * (pane as u32),
};
let close_at = |pane: usize| open_at(pane) + width_of(pane, case.ratio) + close_slop;
match case.phase {
Phase::Locked => {
let ids: Vec<BracketId> = (0..n)
.map(|pane| log.open_bracket(SourceId(pane), open_at(pane), stamps(&paths)))
.collect();
for (w, r) in &case.shape.edges {
*seq += 1;
touch(&dir.join(format!("p{w}_{r}")), *seq);
}
for (pane, id) in ids.iter().enumerate() {
let closed = log
.close_bracket(*id, close_at(pane), stamps(&paths))
.cloned();
if case.production == Production::Driven
&& let Some(closed) = closed
{
let others = log.overlapping(&closed);
ledger.observe_bracket(&closed, &others);
}
}
if case.production == Production::Synthetic {
for (w, r) in &case.shape.edges {
let mut containing = vec![(SourceId(*w), ids[*w])];
for (pane, id) in ids.iter().enumerate() {
if pane != *w {
containing.push((SourceId(pane), *id));
}
}
ledger.inject(
&dir.join(format!("p{w}_{r}")),
open_at(*w) + std::time::Duration::from_millis(1),
containing,
);
}
}
}
Phase::Dephased => {
for pane in 0..n {
let id = log.open_bracket(SourceId(pane), open_at(pane), stamps(&paths));
for (w, r) in &case.shape.edges {
if *w == pane {
*seq += 1;
touch(&dir.join(format!("p{w}_{r}")), *seq);
}
}
let closed = log
.close_bracket(id, close_at(pane), stamps(&paths))
.cloned();
match case.production {
Production::Driven => {
if let Some(closed) = closed {
let others = log.overlapping(&closed);
ledger.observe_bracket(&closed, &others);
}
}
Production::Synthetic => {
for (w, r) in &case.shape.edges {
if *w == pane {
ledger.inject(
&dir.join(format!("p{w}_{r}")),
open_at(pane) + std::time::Duration::from_millis(1),
vec![(SourceId(pane), id)],
);
}
}
}
}
}
}
}
}
let now = t0 + step * (CHANGES as u32) + std::time::Duration::from_secs(1);
let watched: Vec<Vec<std::path::PathBuf>> = (0..n)
.map(|r| {
case.shape
.edges
.iter()
.filter(|(_, watcher)| *watcher == r)
.map(|(w, _)| dir.join(format!("p{w}_{r}")))
.collect()
})
.collect();
let panes: Vec<PaneWindow<'_>> = (0..n)
.map(|id| PaneWindow {
source: SourceId(id),
trigger_respawns: log.respawns_in_window(SourceId(id), now),
watched: &watched[id],
readers: &[],
})
.collect();
LoopSuspicion {
window: W,
min_respawns: MIN_RESPAWNS,
..LoopSuspicion::default()
}
.evaluate(now, &ledger, &log, &panes)
}
fn all_cases() -> Vec<(String, Shape)> {
let mut out: Vec<(String, Shape)> = Vec::new();
for n in 1..=3 {
for shape in shapes(n) {
out.push((format!("n{n}:{:?}", shape.edges), shape));
}
}
for (name, shape) in named() {
out.push((name.to_string(), shape));
}
out
}
#[test]
fn a_co_running_producer_and_consumer_is_not_a_loop() {
let dir = tempfile::tempdir().unwrap();
let mut seq = 1_700_000_000u64;
for ratio in RATIOS {
for close in [Close::Worker, Close::Drain] {
for production in [Production::Synthetic, Production::Driven] {
let case = Case {
shape: Shape {
n: 2,
edges: vec![(0, 1)],
},
ratio,
close,
phase: Phase::Locked,
production,
};
let v = evaluate_case(dir.path(), &case, &mut seq);
assert!(
v.panes.is_empty(),
"accused a legitimate producer-consumer pair: \
ratio={ratio} close={close:?} prod={production:?} -> {:?}",
v.panes
);
}
}
}
}
#[test]
fn condition_four_holds_over_the_bounded_domain_when_children_do_not_overlap() {
let (cells, abstained, failures) = run_matrix(&[Phase::Dephased]);
assert!(
failures.is_empty(),
"{cells} cells, {abstained} abstained, {} failures:\n{}",
failures.len(),
failures.join("\n")
);
}
#[test]
#[ignore = "records the fully-overlapped regime, where the evidence is degenerate; see the doc comment"]
fn condition_four_over_the_bounded_graph_domain() {
let (cells, abstained, failures) = run_matrix(&[Phase::Locked, Phase::Dephased]);
assert!(
failures.is_empty(),
"{cells} cells, {abstained} abstained, {} failures:\n{}",
failures.len(),
failures.join("\n")
);
}
fn run_matrix(phases: &[Phase]) -> (usize, usize, Vec<String>) {
let dir = tempfile::tempdir().unwrap();
let mut seq = 1_700_000_000u64;
let mut failures: Vec<String> = Vec::new();
let mut cells = 0usize;
let mut abstained = 0usize;
for (name, shape) in all_cases() {
let cyclic = shape.has_cycle();
for ratio in RATIOS {
for close in [Close::Worker, Close::Drain] {
for phase in phases.iter().copied() {
for production in [Production::Synthetic, Production::Driven] {
let case = Case {
shape: shape.clone(),
ratio,
close,
phase,
production,
};
let v = evaluate_case(dir.path(), &case, &mut seq);
cells += 1;
if v.abstained {
abstained += 1;
}
if v.abstained {
continue; }
if v.panes.is_empty() == cyclic {
failures.push(format!(
"{name} cyclic={cyclic} ratio={ratio} close={close:?} \
phase={phase:?} prod={production:?} -> panes={:?} abstained={}",
v.panes, v.abstained
));
}
}
}
}
}
}
(cells, abstained, failures)
}
}