use core::cell::Cell;
use super::*;
use crate::metis::dot::RawDot;
fn woven(root: (u32, u64)) -> Dot {
Dot::try_from(root).expect("a fixture root has a nonzero counter")
}
#[derive(Default)]
struct Trace {
next: Cell<u8>,
topology: Option<u8>,
record: Option<u8>,
phases: [Option<(u8, u8)>; 4],
work: TraceWork,
cycle_windows: Vec<(u8, u8)>,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct TraceWork {
play_search_visits: usize,
suffix_start: usize,
raw_suffix_len: usize,
applied_plays_unwound: usize,
refused_plays_skipped_unwind: usize,
superseded_plays_removed: usize,
replay_len: usize,
cycle: TraceCycleWork,
locus_replacements: usize,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct TraceCycleWork {
guards_skipped: usize,
self_guard_entries: usize,
live_guard_entries: usize,
stale_guard_entries: usize,
coordinate_queries: usize,
chain_nodes_visited: usize,
not_descendant_terminals: usize,
origin_terminals: usize,
unborn_terminals: usize,
anchor_cycle_terminals: usize,
invariant_refusals: usize,
refusals: usize,
}
#[derive(Clone, Debug, PartialEq, Eq)]
struct TraceOutput {
topology: u8,
record: u8,
phases: [(u8, u8); 4],
cycle_windows: Vec<(u8, u8)>,
work: TraceWork,
}
impl Trace {
fn new() -> Self {
Self::default()
}
}
impl MovementObserver for Trace {
const OBSERVES_CYCLE_DETAILS: bool = true;
type Mark = u8;
type Output = TraceOutput;
fn mark(&self) -> Self::Mark {
let mark = self.next.get();
self.next.set(mark + 1);
mark
}
fn play_searched(
&mut self,
since: Self::Mark,
until: Self::Mark,
visits: usize,
suffix_start: usize,
raw_suffix_len: usize,
) {
self.phases[0] = Some((since, until));
self.work.play_search_visits = visits;
self.work.suffix_start = suffix_start;
self.work.raw_suffix_len = raw_suffix_len;
}
fn suffix_unwound(
&mut self,
since: Self::Mark,
until: Self::Mark,
applied: usize,
refused: usize,
) {
self.phases[1] = Some((since, until));
self.work.applied_plays_unwound = applied;
self.work.refused_plays_skipped_unwind = refused;
}
fn suffix_edited(
&mut self,
since: Self::Mark,
until: Self::Mark,
superseded: usize,
replay_len: usize,
) {
self.phases[2] = Some((since, until));
self.work.superseded_plays_removed = superseded;
self.work.replay_len = replay_len;
}
fn cycle_checked(&mut self, since: Self::Mark, until: Self::Mark, check: CycleCheck) {
self.cycle_windows.push((since, until));
match check {
CycleCheck::Skipped => self.work.cycle.guards_skipped += 1,
CycleCheck::Coordinate { guard, terminal } => {
match guard {
EnteredCycleGuard::SelfAnchor => self.work.cycle.self_guard_entries += 1,
EnteredCycleGuard::LiveChild => self.work.cycle.live_guard_entries += 1,
EnteredCycleGuard::StaleMonotone => {
self.work.cycle.stale_guard_entries += 1;
}
}
self.work.cycle.coordinate_queries += 1;
match terminal {
CycleTerminal::NotDescendant => {
self.work.cycle.not_descendant_terminals += 1;
}
CycleTerminal::Origin => self.work.cycle.origin_terminals += 1,
CycleTerminal::Unborn => self.work.cycle.unborn_terminals += 1,
CycleTerminal::AnchorCycle => self.work.cycle.anchor_cycle_terminals += 1,
CycleTerminal::InvariantViolation => {
self.work.cycle.invariant_refusals += 1;
}
CycleTerminal::Target => self.work.cycle.refusals += 1,
}
}
CycleCheck::Walk { guard, walk } => {
match guard {
EnteredCycleGuard::SelfAnchor => self.work.cycle.self_guard_entries += 1,
EnteredCycleGuard::LiveChild => self.work.cycle.live_guard_entries += 1,
EnteredCycleGuard::StaleMonotone => {
self.work.cycle.stale_guard_entries += 1;
}
}
self.work.cycle.chain_nodes_visited += walk.nodes_visited;
match walk.terminal {
CycleTerminal::NotDescendant => {
self.work.cycle.not_descendant_terminals += 1;
}
CycleTerminal::Origin => self.work.cycle.origin_terminals += 1,
CycleTerminal::Unborn => self.work.cycle.unborn_terminals += 1,
CycleTerminal::AnchorCycle => self.work.cycle.anchor_cycle_terminals += 1,
CycleTerminal::InvariantViolation => self.work.cycle.invariant_refusals += 1,
CycleTerminal::Target => self.work.cycle.refusals += 1,
}
}
}
}
fn locus_replaced(&mut self) {
self.work.locus_replacements += 1;
}
fn suffix_replayed(&mut self, since: Self::Mark, until: Self::Mark) {
self.phases[3] = Some((since, until));
}
fn topology_placed(&mut self, since: Self::Mark) {
self.topology = Some(since);
}
fn record_composed(&mut self, since: Self::Mark) {
self.record = Some(since);
}
fn finish(self) -> Self::Output {
TraceOutput {
topology: self.topology.expect("topology placement closes"),
record: self.record.expect("record composition closes"),
phases: self
.phases
.map(|phase| phase.expect("every topology phase closes")),
cycle_windows: self.cycle_windows,
work: self.work,
}
}
}
struct MarkPanics;
impl MovementObserver for MarkPanics {
type Mark = ();
type Output = ();
fn mark(&self) -> Self::Mark {
panic!("validation must precede the first phase mark")
}
fn play_searched(&mut self, (): Self::Mark, (): Self::Mark, _: usize, _: usize, _: usize) {}
fn suffix_unwound(&mut self, (): Self::Mark, (): Self::Mark, _: usize, _: usize) {}
fn suffix_edited(&mut self, (): Self::Mark, (): Self::Mark, _: usize, _: usize) {}
fn cycle_checked(&mut self, (): Self::Mark, (): Self::Mark, _: CycleCheck) {}
fn locus_replaced(&mut self) {}
fn suffix_replayed(&mut self, (): Self::Mark, (): Self::Mark) {}
fn topology_placed(&mut self, (): Self::Mark) {}
fn record_composed(&mut self, (): Self::Mark) {}
fn finish(self) -> Self::Output {}
}
fn fixture() -> (Rhapsody, [(u32, u64); 2]) {
let mut text = Rhapsody::new();
let roots = [(1, 1), (1, 2)];
for (logical, root) in roots.into_iter().enumerate() {
assert!(text.weave(
woven(root),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(1, u16::try_from(logical).unwrap(), 1, 0u16),
},
));
}
(text, roots)
}
#[test]
fn unavailable_ancestry_refuses_before_the_batch_callback() {
let (text, _) = fixture();
let mut moves = Composer::new(2);
let mut reading = text.recension(moves.state().store());
let failure = CoordinateError::CapacityExceeded {
nodes: 2,
maximum: 1,
};
reading.ancestry = Err(failure);
let called = Cell::new(false);
assert_eq!(
reading.with_movement_batch(&text, &mut moves, |_| called.set(true)),
Err(MovementBatchError::AncestryUnavailable(failure))
);
assert!(!called.get());
assert!(moves.state().store().is_empty());
assert!(matches!(reading.ancestry, Err(error) if error == failure));
}
fn assert_cycle_accounting(work: TraceCycleWork, replay_len: usize) {
let entered = work.self_guard_entries + work.live_guard_entries + work.stale_guard_entries;
assert_eq!(replay_len, work.guards_skipped + entered);
assert_eq!(
entered,
work.not_descendant_terminals
+ work.origin_terminals
+ work.unborn_terminals
+ work.anchor_cycle_terminals
+ work.invariant_refusals
+ work.refusals
);
}
#[test]
fn a_short_non_target_anchor_cycle_stops_before_the_skeleton_budget() {
let target = RawDot::new(1, 3);
let anchored = BTreeSet::from([target]);
let outcome = move_forms_a_cycle(
target,
Anchor::After(RawDot {
station: 1,
counter: 1,
}),
&anchored,
WalkBudget::for_skeleton(1_000),
|at| match (at.station, at.counter) {
(1, 1) => Some(Some(RawDot::new(1, 2))),
(1, 2) => Some(Some(RawDot::new(1, 1))),
_ => None,
},
);
let CycleOutcome::Walk(walk) = outcome else {
panic!("the monotone guard enters the walk");
};
assert!(matches!(walk.terminal, CycleTerminal::AnchorCycle));
assert_eq!(walk.nodes_visited, 4);
assert!(!outcome.must_refuse());
}
#[test]
fn brent_detection_is_bounded_by_the_reachable_functional_graph() {
for prefix_len in 0usize..32 {
for cycle_len in 1usize..32 {
let distinct = prefix_len + cycle_len;
let walk = |padding| {
let target = RawDot::new(2, 1);
let anchored = BTreeSet::from([target]);
let outcome = move_forms_a_cycle(
target,
Anchor::After(RawDot {
station: 1,
counter: 1,
}),
&anchored,
WalkBudget::for_skeleton(distinct + 1 + padding),
|at| {
let index = usize::try_from(at.counter).expect("the fixture index fits");
let next = if index < distinct {
index + 1
} else {
prefix_len + 1
};
Some(Some(RawDot::new(
1,
u64::try_from(next).expect("the fixture fits"),
)))
},
);
let CycleOutcome::Walk(walk) = outcome else {
panic!("the monotone guard enters the walk");
};
assert!(matches!(walk.terminal, CycleTerminal::AnchorCycle));
assert!(!outcome.must_refuse());
walk
};
let compact = walk(0);
let padded = walk(1_000);
assert_eq!(compact.nodes_visited, padded.nodes_visited);
assert!(compact.nodes_visited <= distinct.saturating_mul(3).saturating_add(1));
}
}
}
#[test]
fn an_impossible_lookup_that_exceeds_the_defensive_budget_refuses() {
let target = RawDot::new(1, 1);
let anchored = BTreeSet::from([target]);
let outcome = move_forms_a_cycle(
target,
Anchor::After(RawDot {
station: 2,
counter: 1,
}),
&anchored,
WalkBudget::for_skeleton(1),
|at| Some(Some(RawDot::new(at.station, at.counter + 1))),
);
let CycleOutcome::Walk(walk) = outcome else {
panic!("the monotone guard enters the walk");
};
assert!(matches!(walk.terminal, CycleTerminal::InvariantViolation));
assert_eq!(walk.nodes_visited, 4);
assert!(outcome.must_refuse());
}
#[test]
fn an_unborn_terminus_does_not_exhaust_the_walk_budget() {
let target = RawDot::new(1, 1);
let anchored = BTreeSet::from([target]);
let outcome = move_forms_a_cycle(
target,
Anchor::After(RawDot {
station: 1,
counter: 2,
}),
&anchored,
WalkBudget::for_skeleton(3),
|at| match (at.station, at.counter) {
(1, 2) => Some(Some(RawDot::new(1, 3))),
(1, 3) => Some(Some(RawDot::new(9, 9))),
_ => None,
},
);
let CycleOutcome::Walk(walk) = outcome else {
panic!("the monotone guard enters the walk");
};
assert!(matches!(walk.terminal, CycleTerminal::Unborn));
assert_eq!(walk.nodes_visited, 3);
assert!(!outcome.must_refuse());
}
#[test]
fn validation_precedes_disjoint_topology_and_record_phase_marks() {
let (text, roots) = fixture();
let mut moves = Composer::new(2);
let mut reading = text.recension(moves.state().store());
reading
.with_movement_batch(&text, &mut moves, |batch| {
assert!(matches!(
batch.move_to_observed(
RawDot::new(9, 9),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(2, 0, 2, 0u16),
},
MarkPanics,
),
Err(MovementBatchError::UnknownTarget { .. })
));
let (_, trace) = batch
.move_to_observed(
roots[1].into(),
Locus {
anchor: Anchor::After(roots[0].into()),
rank: Kairos::new(2, 1, 2, 0u16),
},
Trace::new(),
)
.expect("the forward move applies");
assert_eq!(trace.topology, 0);
assert_eq!(trace.phases, [(1, 2), (3, 4), (5, 6), (7, 10)]);
assert_eq!(trace.cycle_windows, [(8, 9)]);
assert_eq!(trace.record, 11);
assert_eq!(
trace.work,
TraceWork {
replay_len: 1,
cycle: TraceCycleWork {
guards_skipped: 1,
..TraceCycleWork::default()
},
locus_replacements: 1,
..TraceWork::default()
}
);
assert_cycle_accounting(trace.work.cycle, trace.work.replay_len);
})
.expect("the fixture is fully placed");
}
#[test]
fn an_early_target_reports_the_raw_and_edited_suffixes() {
let mut text = Rhapsody::new();
let roots = [(1, 1), (1, 2), (1, 3)];
for (logical, root) in roots.into_iter().enumerate() {
assert!(text.weave(
woven(root),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(1, u16::try_from(logical).unwrap(), 1, 0u16),
},
));
}
let mut moves = Composer::new(2);
let mut reading = text.recension(moves.state().store());
reading
.with_movement_batch(&text, &mut moves, |batch| {
for (logical, (target, anchor)) in [(roots[1], roots[0]), (roots[2], roots[1])]
.into_iter()
.enumerate()
{
let _ = batch
.move_to(
target.into(),
Locus {
anchor: Anchor::After(anchor.into()),
rank: Kairos::new(2, u16::try_from(logical).unwrap(), 2, 0u16),
},
)
.expect("the setup move applies");
}
let (_, trace) = batch
.move_to_observed(
roots[1].into(),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(2, 2, 2, 0u16),
},
Trace::new(),
)
.expect("the early target replays its suffix");
assert_eq!(
trace.work,
TraceWork {
play_search_visits: 1,
suffix_start: 0,
raw_suffix_len: 2,
applied_plays_unwound: 2,
superseded_plays_removed: 1,
replay_len: 2,
cycle: TraceCycleWork {
guards_skipped: 2,
..TraceCycleWork::default()
},
locus_replacements: 2,
..TraceWork::default()
}
);
assert_cycle_accounting(trace.work.cycle, trace.work.replay_len);
assert_eq!(
trace.work.raw_suffix_len,
trace.work.applied_plays_unwound + trace.work.refused_plays_skipped_unwind
);
assert_eq!(
trace.work.replay_len,
trace.work.raw_suffix_len - trace.work.superseded_plays_removed + 1
);
})
.expect("the fixture is fully placed");
}
#[test]
fn a_refused_play_is_counted_in_cycle_and_unwind_work() {
let (text, roots) = fixture();
let mut moves = Composer::new(2);
let mut reading = text.recension(moves.state().store());
reading
.with_movement_batch(&text, &mut moves, |batch| {
let (_, refused) = batch
.move_to_observed(
roots[1].into(),
Locus {
anchor: Anchor::After(roots[1].into()),
rank: Kairos::new(2, 0, 2, 0u16),
},
Trace::new(),
)
.expect("a cycle-former remains valid record state");
assert_eq!(
refused.work,
TraceWork {
replay_len: 1,
cycle: TraceCycleWork {
self_guard_entries: 1,
coordinate_queries: 1,
refusals: 1,
..TraceCycleWork::default()
},
..TraceWork::default()
}
);
assert_cycle_accounting(refused.work.cycle, refused.work.replay_len);
let (_, replacement) = batch
.move_to_observed(
roots[1].into(),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(2, 1, 2, 0u16),
},
Trace::new(),
)
.expect("the later testimony supersedes the refusal");
assert_eq!(replacement.work.raw_suffix_len, 1);
assert_eq!(replacement.work.applied_plays_unwound, 0);
assert_eq!(replacement.work.refused_plays_skipped_unwind, 1);
assert_eq!(replacement.work.superseded_plays_removed, 1);
assert_eq!(replacement.work.replay_len, 1);
assert_eq!(replacement.work.locus_replacements, 1);
})
.expect("the fixture is fully placed");
}
#[test]
fn an_origin_move_bypasses_a_stale_guard_entry() {
let (text, roots) = fixture();
let mut moves = Composer::new(2);
let mut reading = text.recension(moves.state().store());
reading
.with_movement_batch(&text, &mut moves, |batch| {
for (logical, anchor) in [Anchor::After(roots[1].into()), Anchor::Origin]
.into_iter()
.enumerate()
{
let _ = batch
.move_to(
roots[0].into(),
Locus {
anchor,
rank: Kairos::new(2, u16::try_from(logical).unwrap(), 2, 0u16),
},
)
.expect("the child moves away from its former anchor");
}
let (_, trace) = batch
.move_to_observed(
roots[1].into(),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(2, 2, 2, 0u16),
},
Trace::new(),
)
.expect("the stale guard entry remains semantically safe");
assert_eq!(
trace.work.cycle,
TraceCycleWork {
guards_skipped: 1,
..TraceCycleWork::default()
}
);
assert_cycle_accounting(trace.work.cycle, trace.work.replay_len);
})
.expect("the fixture is fully placed");
}
#[test]
fn a_deep_ready_refusal_uses_one_coordinate_query() {
let mut text = Rhapsody::new();
let roots = [(1, 1), (1, 2), (1, 3)];
for (logical, root) in roots.into_iter().enumerate() {
assert!(text.weave(
woven(root),
Locus {
anchor: Anchor::Origin,
rank: Kairos::new(1, u16::try_from(logical).unwrap(), 1, 0u16),
},
));
}
let mut moves = Composer::new(2);
let mut reading = text.recension(moves.state().store());
reading
.with_movement_batch(&text, &mut moves, |batch| {
for (logical, (target, anchor)) in [(roots[1], roots[0]), (roots[2], roots[1])]
.into_iter()
.enumerate()
{
let _ = batch
.move_to(
target.into(),
Locus {
anchor: Anchor::After(anchor.into()),
rank: Kairos::new(2, u16::try_from(logical).unwrap(), 2, 0u16),
},
)
.expect("the setup extends the effective chain");
}
let (_, trace) = batch
.move_to_observed(
roots[0].into(),
Locus {
anchor: Anchor::After(roots[2].into()),
rank: Kairos::new(2, 2, 2, 0u16),
},
Trace::new(),
)
.expect("a cycle-former remains valid record state");
assert_eq!(
trace.work.cycle,
TraceCycleWork {
live_guard_entries: 1,
coordinate_queries: 1,
refusals: 1,
..TraceCycleWork::default()
}
);
assert_cycle_accounting(trace.work.cycle, trace.work.replay_len);
})
.expect("the fixture is fully placed");
}