use super::Graph;
use std::sync::{Arc, atomic::AtomicBool};
fn insert(graph: &mut Graph, parents: &[usize]) -> usize {
graph.insert(parents, Arc::new(AtomicBool::new(false)))
}
#[test]
fn pruning_preserves_diamond_ancestry_without_cancelling_siblings() {
for cancelled_parent in [0, 1] {
let mut graph = Graph::default();
let roots = [insert(&mut graph, &[]), insert(&mut graph, &[])];
let intermediate = insert(&mut graph, &roots);
let left = insert(&mut graph, &[intermediate, roots[0]]);
let right = insert(&mut graph, &[intermediate]);
let unrelated = insert(&mut graph, &[]);
graph.remove(intermediate);
assert_eq!(graph.snapshot(), (5, 1, 5));
graph.cancel(roots[cancelled_parent]);
assert!(graph.is_cancelled(left));
assert!(graph.is_cancelled(right));
assert!(!graph.is_cancelled(roots[1 - cancelled_parent]));
assert!(!graph.is_cancelled(unrelated));
}
}
#[test]
fn cancellation_and_reclamation_of_a_live_deep_chain_are_iterative() {
std::thread::Builder::new()
.stack_size(128 * 1024)
.spawn(|| {
let mut graph = Graph::default();
let root = insert(&mut graph, &[]);
let mut previous = root;
for _ in 0..100_000 {
previous = insert(&mut graph, &[previous]);
}
graph.cancel(root);
assert!(graph.is_cancelled(previous));
for id in 0..100_000 {
graph.remove(id);
}
assert_eq!(graph.snapshot(), (1, 0, 0));
graph.remove(previous);
assert_eq!(graph.snapshot(), (0, 0, 0));
})
.unwrap()
.join()
.unwrap();
}
#[test]
fn every_pruning_subset_preserves_reachability_in_a_branching_owner_graph() {
let parents: [&[usize]; 8] = [&[], &[0], &[0], &[1, 2], &[1], &[3], &[4, 5], &[2]];
for removed in 0..256 {
for cancelled in 0..8 {
if removed & (1 << cancelled) != 0 {
continue;
}
let mut graph = Graph::default();
for links in parents {
insert(&mut graph, links);
}
for id in 0..8 {
if removed & (1 << id) != 0 {
graph.remove(id);
}
}
graph.cancel(cancelled);
let mut expected = [false; 8];
for id in 0..8 {
expected[id] = id == cancelled || parents[id].iter().any(|p| expected[*p]);
if removed & (1 << id) == 0 {
assert_eq!(
graph.is_cancelled(id),
expected[id],
"mask={removed} cancel={cancelled} node={id}"
);
}
}
assert_eq!(
graph.nodes.len(),
8 - (removed as u32).count_ones() as usize
);
for (id, node) in &graph.nodes {
for child in &node.children {
assert!(graph.nodes[child].parents.contains(id));
assert!(child > id);
}
}
}
}
}
#[test]
fn pruning_a_many_owner_fanout_does_not_materialize_the_cross_product() {
const OWNERS: usize = 256;
const CHILDREN: usize = 5_000;
let mut graph = Graph::default();
let owners = (0..OWNERS)
.map(|_| insert(&mut graph, &[]))
.collect::<Vec<_>>();
let mut bridge = insert(&mut graph, &[owners[0]]);
for owner in owners.iter().skip(1) {
let next = insert(&mut graph, &[bridge, *owner]);
graph.remove(bridge);
bridge = next;
}
let children = (0..CHILDREN)
.map(|_| insert(&mut graph, &[bridge]))
.collect::<Vec<_>>();
let started = std::time::Instant::now();
graph.remove(bridge);
let elapsed = started.elapsed();
let (nodes, relays, edges) = graph.snapshot();
assert_eq!(nodes, OWNERS + CHILDREN);
assert_eq!(relays, 1);
assert!(
edges <= OWNERS + CHILDREN + 1,
"dense pruning retained {nodes} nodes and {edges} edges in {elapsed:?}"
);
graph.cancel(owners[OWNERS / 2]);
assert!(children.iter().all(|id| graph.is_cancelled(*id)));
assert!(
owners
.iter()
.enumerate()
.all(|(index, id)| graph.is_cancelled(*id) == (index == OWNERS / 2))
);
}
#[test]
fn repeated_branching_and_reconvergence_does_not_retain_relay_history() {
let mut graph = Graph::default();
let roots = [
insert(&mut graph, &[]),
insert(&mut graph, &[]),
insert(&mut graph, &[]),
];
let mut layer = [
insert(&mut graph, &[roots[0], roots[1]]),
insert(&mut graph, &[roots[1], roots[2]]),
insert(&mut graph, &[roots[0], roots[2]]),
];
for generation in 0..1_000 {
let next = [
insert(&mut graph, &[layer[0], layer[1]]),
insert(&mut graph, &[layer[1], layer[2]]),
insert(&mut graph, &[layer[0], layer[2]]),
];
for id in layer {
graph.remove(id);
}
layer = next;
let (tokens, relays, links) = graph.snapshot();
assert_eq!(tokens, 6);
assert!(relays <= 6, "generation {generation}: {relays} relays");
assert!(links <= 18, "generation {generation}: {links} links");
}
graph.cancel(roots[0]);
assert!(layer.iter().all(|id| graph.is_cancelled(*id)));
assert!(!graph.is_cancelled(roots[1]));
assert!(!graph.is_cancelled(roots[2]));
}
#[test]
fn equivalent_relays_with_different_history_preserve_future_cancellation() {
let mut graph = Graph::default();
let p = insert(&mut graph, &[]);
let q = insert(&mut graph, &[]);
let retired = insert(&mut graph, &[]);
let prefix = insert(&mut graph, &[p, q]);
let old = insert(&mut graph, &[prefix, retired]);
graph.remove(prefix);
let old_children = [insert(&mut graph, &[old]), insert(&mut graph, &[old])];
graph.cancel(retired);
graph.remove(old);
graph.remove(retired);
let fresh = insert(&mut graph, &[p, q]);
let fresh_children = [insert(&mut graph, &[fresh]), insert(&mut graph, &[fresh])];
graph.remove(fresh);
assert!(old_children.iter().all(|id| graph.is_cancelled(*id)));
assert!(fresh_children.iter().all(|id| !graph.is_cancelled(*id)));
graph.cancel(p);
assert!(fresh_children.iter().all(|id| graph.is_cancelled(*id)));
}
#[test]
fn unique_owner_prefix_relays_do_not_flatten_live_ancestry() {
const OWNERS: usize = 2_000;
let mut graph = Graph::default();
let owners = (0..OWNERS)
.map(|_| insert(&mut graph, &[]))
.collect::<Vec<_>>();
let mut bridge = insert(&mut graph, &[owners[0], owners[1]]);
let mut leaves = Vec::new();
for owner in owners.iter().skip(2) {
let next = insert(&mut graph, &[bridge, *owner]);
leaves.push(insert(&mut graph, &[bridge]));
leaves.push(insert(&mut graph, &[bridge]));
graph.remove(bridge);
bridge = next;
}
leaves.push(insert(&mut graph, &[bridge]));
leaves.push(insert(&mut graph, &[bridge]));
graph.remove(bridge);
let (tokens, relays, links) = graph.snapshot();
assert_eq!(tokens, OWNERS + leaves.len());
assert_eq!(relays, OWNERS - 1);
assert!(
links <= 4 * relays,
"{relays} relays retained {links} links"
);
let build = graph.work_snapshot();
assert!(
build.union_items <= 2 * OWNERS,
"construction iterated {} ancestry items",
build.union_items
);
assert!(
build.allocated_nodes <= (usize::BITS as usize + 2) * OWNERS,
"construction allocated {} Patricia nodes",
build.allocated_nodes
);
assert_eq!(build.equality_nodes, 0);
assert_eq!(build.candidate_checks, 0);
assert_eq!(build.topology_rebuilds, 0);
assert_eq!(build.relay_checks, relays);
assert!(graph.nodes.values().all(|entry| {
entry.kind != super::Kind::Relay || (entry.parents.len() > 1 && entry.children.len() > 1)
}));
graph.reset_work();
graph.cancel(owners[0]);
let cancellation = graph.work_snapshot();
assert_eq!(cancellation.union_items, 0);
assert_eq!(cancellation.equality_nodes, 0);
assert_eq!(cancellation.allocated_nodes, 0);
assert_eq!(cancellation.candidate_checks, 0);
assert_eq!(cancellation.topology_rebuilds, 0);
assert_eq!(cancellation.relay_checks, relays);
assert!(leaves.iter().all(|id| graph.is_cancelled(*id)));
}