use std::{
collections::{BTreeMap, BTreeSet},
sync::{
Arc,
atomic::{AtomicBool, Ordering},
},
};
#[path = "cancellation_signature.rs"]
mod signature;
use signature::{Candidate, Signature};
#[path = "cancellation_graph_normalize.rs"]
mod normalize;
#[path = "cancellation_graph_rewrite.rs"]
mod rewrite;
use normalize::RelayWork;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum Kind {
Token,
Relay,
}
struct Entry {
kind: Kind,
flag: Option<Arc<AtomicBool>>,
cancelled: bool,
parents: BTreeSet<usize>,
children: BTreeSet<usize>,
signature: Signature,
}
#[cfg(test)]
#[derive(Clone, Copy, Debug, Default)]
pub(super) struct WorkSnapshot {
pub(super) union_items: usize,
pub(super) equality_nodes: usize,
pub(super) allocated_nodes: usize,
pub(super) candidate_checks: usize,
pub(super) relay_checks: usize,
pub(super) topology_rebuilds: usize,
}
#[derive(Default)]
pub(super) struct Graph {
next: usize,
relays: usize,
nodes: BTreeMap<usize, Entry>,
relay_index: BTreeMap<Candidate, BTreeSet<usize>>,
#[cfg(test)]
work: WorkSnapshot,
}
impl Graph {
pub(super) fn insert(&mut self, parents: &[usize], flag: Arc<AtomicBool>) -> usize {
let id = self.next;
self.next = self
.next
.checked_add(1)
.expect("cancellation identity exhausted");
let parents = parents.iter().copied().collect::<BTreeSet<_>>();
let cancelled = parents.iter().any(|parent| self.nodes[parent].cancelled);
flag.store(cancelled, Ordering::Release);
for parent in &parents {
self.nodes
.get_mut(parent)
.expect("live parent")
.children
.insert(id);
}
self.nodes.insert(
id,
Entry {
kind: Kind::Token,
flag: Some(flag),
cancelled,
parents,
children: BTreeSet::new(),
signature: Signature::singleton(id),
},
);
id
}
pub(super) fn remove(&mut self, id: usize) {
let (parents, children, inherited, relay) = {
let entry = self.nodes.get(&id).expect("live cancellation node");
assert_eq!(entry.kind, Kind::Token, "token removed twice");
(
entry.parents.clone(),
entry.children.clone(),
entry
.parents
.iter()
.any(|parent| self.nodes[parent].cancelled),
entry.parents.len() > 1 && entry.children.len() > 1,
)
};
if relay {
let signature = self.signature_for(&parents);
let entry = self.nodes.get_mut(&id).expect("live cancellation node");
entry.kind = Kind::Relay;
entry.flag = None;
entry.cancelled = inherited;
entry.signature = signature;
self.relays += 1;
self.index_relay(id);
self.normalize(
std::iter::once(RelayWork::known(id))
.chain(children.into_iter().map(RelayWork::dirty)),
);
} else {
let affected = self.erase(id, true, true);
self.normalize(affected);
}
}
pub(super) fn cancel(&mut self, id: usize) {
let mut pending = vec![id];
let mut changed_relays = Vec::new();
while let Some(id) = pending.pop() {
let children = {
let node = self.nodes.get_mut(&id).expect("live cancellation path");
if node.cancelled {
continue;
}
node.cancelled = true;
if let Some(flag) = &node.flag {
flag.store(true, Ordering::Release);
} else {
changed_relays.push(id);
}
node.children.iter().copied().collect::<Vec<_>>()
};
pending.extend(children);
}
self.normalize(changed_relays.into_iter().map(RelayWork::known));
}
pub(super) fn is_cancelled(&self, id: usize) -> bool {
self.nodes[&id].cancelled
}
#[cfg(test)]
pub(super) fn snapshot(&self) -> (usize, usize, usize) {
let tokens = self
.nodes
.values()
.filter(|entry| entry.kind == Kind::Token)
.count();
let links = self.nodes.values().map(|entry| entry.children.len()).sum();
(tokens, self.relays, links)
}
#[cfg(test)]
pub(super) fn work_snapshot(&self) -> WorkSnapshot {
self.work
}
#[cfg(test)]
pub(super) fn reset_work(&mut self) {
self.work = WorkSnapshot::default();
}
#[cfg(test)]
fn record_signature_work(&mut self, work: signature::Work) {
self.work.union_items += work.union_items;
self.work.equality_nodes += work.equality_nodes;
self.work.allocated_nodes += work.allocated_nodes;
}
}
#[cfg(test)]
#[path = "cancellation_graph_test.rs"]
mod cancellation_graph_test;
#[cfg(test)]
#[path = "cancellation_graph_differential_test.rs"]
mod cancellation_graph_differential_test;