extern crate std;
use alloc::collections::{BTreeMap, BTreeSet};
use proptest::prelude::*;
use super::*;
use crate::kairos::Kairos;
use crate::metis::rhapsody::Anchor;
fn rank(at: u64) -> Kairos {
Kairos::new(at, 0, 1, 0u16)
}
fn d(station: u32, counter: u64) -> Dot {
Dot::from_parts(station, counter).expect("a test dot has a nonzero counter")
}
fn locus(parent: Option<Dot>, at: u64) -> Locus {
Locus {
anchor: parent.map_or(Anchor::Origin, |dot| Anchor::After(dot.into())),
rank: rank(at),
}
}
fn plane(entries: impl IntoIterator<Item = (Dot, Locus)>) -> IdentityPlane {
let mut plane = IdentityPlane::new();
plane.extend_ascending(entries);
plane
}
#[test]
fn compact_layout_and_sparse_addressing_are_pinned() {
assert_eq!(core::mem::size_of::<Node>(), 12);
assert_eq!(core::mem::size_of::<Option<NodeId>>(), 4);
let skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 65), locus(None, 2)),
(d(7, u64::MAX), locus(None, 3)),
]);
let coordinate = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
let profile = coordinate.profile();
assert_eq!(profile.resident_nodes, 3);
assert!(profile.node_capacity >= 4);
assert_eq!(profile.address_pages, 3);
assert_eq!(profile.address_page_capacity, 64);
assert_eq!(profile.address_prefix_slots, 2);
assert!(profile.address_prefix_capacity >= 2);
assert_eq!(profile.address_exception_pages, 1);
assert_eq!(profile.station_fibers, 2);
assert_eq!(profile.free_nodes, 0);
assert_eq!(profile.free_node_capacity, 0);
}
#[test]
fn construction_is_transactional_at_the_capacity_boundary() {
let skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 2), locus(Some(d(1, 1)), 2)),
]);
assert!(matches!(
Coordinate::build_with_limit(&skeleton, &BTreeSet::new(), 1),
Err(CoordinateError::CapacityExceeded {
nodes: 2,
maximum: 1,
})
));
}
#[test]
fn unplaced_nodes_are_reserved_and_queries_are_typed() {
let skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 2), locus(Some(d(9, 9)), 2)),
]);
let unplaced = BTreeSet::from([d(1, 2)]);
let mut coordinate = Coordinate::build(&skeleton, &unplaced).unwrap();
assert_eq!(coordinate.profile().resident_nodes, 2);
assert_eq!(
coordinate.relation(d(1, 1), d(1, 1)),
Err(QueryError::UnplacedReading {
first_unplaced: d(1, 2),
})
);
}
#[test]
fn relation_distinguishes_every_ready_result_and_unknown_side() {
let skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 2), locus(Some(d(1, 1)), 2)),
(d(1, 3), locus(Some(d(1, 2)), 3)),
(d(2, 1), locus(None, 4)),
]);
let mut coordinate = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
assert_eq!(coordinate.relation(d(1, 2), d(1, 2)), Ok(Relation::Same));
assert_eq!(
coordinate.relation(d(1, 3), d(1, 1)),
Ok(Relation::Descendant)
);
assert_eq!(
coordinate.relation(d(1, 1), d(1, 3)),
Ok(Relation::NotDescendant)
);
assert_eq!(
coordinate.relation(d(2, 1), d(1, 1)),
Ok(Relation::NotDescendant)
);
assert_eq!(
coordinate.relation(d(9, 9), d(1, 1)),
Err(QueryError::UnknownDescendant { dot: d(9, 9) })
);
assert_eq!(
coordinate.relation(d(1, 1), d(9, 9)),
Err(QueryError::UnknownAncestor { dot: d(9, 9) })
);
assert_eq!(coordinate.addresses.get(d(1, 1)), NodeId::for_index(1));
assert_eq!(coordinate.addresses.get(d(1, 2)), NodeId::for_index(2));
assert_eq!(coordinate.addresses.get(d(1, 3)), NodeId::for_index(3));
assert_eq!(coordinate.addresses.get(d(2, 1)), NodeId::for_index(4));
}
#[test]
fn single_root_builds() {
let skeleton = plane([(d(1, 1), locus(None, 1))]);
let _ = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
}
#[test]
fn construction_rejects_an_invalid_placement_partition() {
let skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 2), locus(Some(d(1, 1)), 2)),
]);
assert!(matches!(
Coordinate::build(&skeleton, &BTreeSet::from([d(1, 2)])),
Err(CoordinateError::InvariantViolation)
));
assert!(matches!(
Coordinate::build(&skeleton, &BTreeSet::from([d(9, 9)])),
Err(CoordinateError::InvariantViolation)
));
}
#[test]
fn construction_links_cross_station_parents_in_both_address_directions() {
let skeleton = plane([
(d(1, 1), locus(Some(d(2, 2)), 2)),
(d(2, 2), locus(None, 1)),
(d(3, 3), locus(Some(d(1, 1)), 3)),
]);
let mut coordinate = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
assert_eq!(
coordinate.relation(d(3, 3), d(2, 2)),
Ok(Relation::Descendant)
);
}
#[test]
fn edge_transitions_preserve_reserved_identity_and_readiness() {
let mut skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 2), locus(Some(d(1, 1)), 2)),
(d(1, 3), locus(Some(d(1, 2)), 3)),
]);
let mut coordinate = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
coordinate.replace_parent(d(1, 2), None).unwrap();
let _ = skeleton.remove(d(1, 2));
assert!(skeleton.insert(d(1, 2), locus(None, 4)));
coordinate.validate(&skeleton, &BTreeSet::new()).unwrap();
assert_eq!(
coordinate.relation(d(1, 3), d(1, 1)),
Ok(Relation::NotDescendant)
);
coordinate.park(d(1, 3)).unwrap();
coordinate.park(d(1, 2)).unwrap();
coordinate.publish_state(Some(d(1, 2)));
let unplaced = BTreeSet::from([d(1, 2), d(1, 3)]);
coordinate.validate(&skeleton, &unplaced).unwrap();
assert_eq!(coordinate.first_unplaced(), Some(d(1, 2)));
coordinate.repair(d(1, 2), None).unwrap();
coordinate.repair(d(1, 3), Some(RawDot::new(1, 2))).unwrap();
coordinate.publish_state(None);
coordinate.validate(&skeleton, &BTreeSet::new()).unwrap();
let dangling = d(7, u64::MAX);
assert!(skeleton.insert(dangling, locus(Some(d(9, 9)), 5)));
coordinate
.add(dangling, Some(RawDot::new(9, 9)), false, Some(dangling))
.unwrap();
coordinate
.validate(&skeleton, &BTreeSet::from([dangling]))
.unwrap();
assert_eq!(coordinate.profile().resident_nodes, 4);
}
#[test]
fn sequential_reparenting_builds_a_deep_chain() {
let mut skeleton = plane([
(d(1, 1), locus(None, 1)),
(d(1, 2), locus(None, 2)),
(d(1, 3), locus(None, 3)),
]);
let mut coordinate = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
coordinate
.replace_parent(d(1, 2), Some(RawDot::new(1, 1)))
.unwrap();
let _ = skeleton.remove(d(1, 2));
assert!(skeleton.insert(d(1, 2), locus(Some(d(1, 1)), 4)));
coordinate
.replace_parent(d(1, 3), Some(RawDot::new(1, 2)))
.unwrap();
let _ = skeleton.remove(d(1, 3));
assert!(skeleton.insert(d(1, 3), locus(Some(d(1, 2)), 5)));
coordinate.validate(&skeleton, &BTreeSet::new()).unwrap();
}
proptest! {
#[test]
fn rooted_coordinate_agrees_with_parent_walk(
parents in proptest::collection::vec(0usize..64, 1..64),
stations in proptest::collection::vec(1u32..5, 1..64),
reverse_dot_order in any::<bool>(),
queries in proptest::collection::vec((0usize..64, 0usize..64), 1..128),
) {
let len = parents.len();
let dots: Vec<Dot> = (0..len)
.map(|offset| {
let index = if reverse_dot_order { len - offset } else { offset + 1 };
d(stations[offset % stations.len()], index as u64)
})
.collect();
let entries: BTreeMap<Dot, Locus> = parents
.into_iter()
.enumerate()
.map(|(offset, candidate)| {
let parent = (candidate < offset).then(|| dots[candidate]);
(dots[offset], locus(parent, offset as u64 + 1))
})
.collect();
let skeleton = plane(entries.iter().map(|(&dot, &locus)| (dot, locus)));
let mut coordinate = Coordinate::build(&skeleton, &BTreeSet::new()).unwrap();
for (descendant, ancestor) in queries {
let descendant = descendant % len;
let ancestor = ancestor % len;
let descendant_dot = dots[descendant];
let ancestor_dot = dots[ancestor];
let expected = if descendant == ancestor {
Relation::Same
} else {
let mut at = descendant_dot;
let mut found = false;
while let Some(parent) = entries[&at]
.anchor
.dot()
.and_then(|raw| Dot::try_from(raw).ok())
{
if parent == ancestor_dot {
found = true;
break;
}
at = parent;
}
if found { Relation::Descendant } else { Relation::NotDescendant }
};
prop_assert_eq!(coordinate.relation(descendant_dot, ancestor_dot), Ok(expected));
}
}
}