Skip to main content

stateknot_core/
recovery.rs

1// Copyright 2026 StateKnot contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Deterministic ready-node replay and crash-recovery planning.
5//!
6//! A plan is derived only from one fully verified checkpoint, its canonical
7//! root-node activations, immutable pending results, complete physical-attempt
8//! histories, one exact live worker fence, and a database-observed timestamp.
9//! It performs no I/O and authorizes no dispatch. Storage/runtime code must
10//! revalidate ownership and commit a durable node-attempt start before invoking
11//! node code; an idempotently observed pre-existing start is in-flight evidence,
12//! not fresh launch authority.
13
14use std::collections::BTreeMap;
15
16use thiserror::Error;
17
18use crate::{
19    BarrierResultHeads, BarrierResultHeadsError, Checkpoint, Failure, JournalHead, NodeActivation,
20    NodeActivationError, NodeAttempt, NodeAttemptHistoryError, NodeAttemptHistoryVerifier,
21    NodeAttemptOutcome, NodeAttemptStartHead, NodeAttemptStatus, NodeId, PendingNodeResult,
22    PendingNodeResultHead, RetryAdvice, RunFence, Timestamp,
23};
24
25/// Stable reason that one logical activation may start a new physical attempt.
26#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
27#[non_exhaustive]
28pub enum NodeDispatchReason {
29    /// No physical attempt has ever started for the activation.
30    FirstAttempt,
31    /// An unfinished attempt belongs to a superseded lower worker fence.
32    SupersededAttempt,
33    /// A failed attempt explicitly authorized a retry whose delay elapsed.
34    SafeRetry,
35}
36
37/// Closed scheduler classification for one checkpoint-ready node.
38#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
39#[non_exhaustive]
40pub enum RecoveryNodeKind {
41    /// An immutable logical result already exists and must be reused.
42    Completed,
43    /// A durable physical start may be prepared after ownership revalidation.
44    Dispatchable,
45    /// A safe retry exists but its database-time delay has not elapsed.
46    Deferred,
47    /// An unfinished attempt already belongs to the current worker fence.
48    InFlight,
49    /// A terminal node failure does not authorize automatic retry.
50    Failed,
51    /// The hard physical-attempt safety ceiling forbids another start.
52    Exhausted,
53}
54
55/// Deterministic recovery decision for one logical ready-node activation.
56#[allow(clippy::large_enum_variant)]
57#[derive(Clone, Debug)]
58#[non_exhaustive]
59pub enum RecoveryNode {
60    /// Reuse a fully verified immutable result without executing the node.
61    Completed {
62        /// Canonical activation derived from the checkpoint.
63        activation: NodeActivation,
64        /// Exact durable result to consume at the barrier.
65        result: PendingNodeResultHead,
66    },
67    /// The runtime may durably start a fresh physical attempt.
68    Dispatchable {
69        /// Canonical activation derived from the checkpoint.
70        activation: NodeActivation,
71        /// Why another physical start is semantically permitted.
72        reason: NodeDispatchReason,
73    },
74    /// The activation must remain durably deferred until database time reaches
75    /// `not_before`.
76    Deferred {
77        /// Canonical activation derived from the checkpoint.
78        activation: NodeActivation,
79        /// Inclusive earliest database instant for a safe successor start.
80        not_before: Timestamp,
81    },
82    /// An unfinished start already belongs to the exact current worker fence.
83    /// Re-execution under the same fence would duplicate in-process work.
84    InFlight {
85        /// Canonical activation derived from the checkpoint.
86        activation: NodeActivation,
87        /// Exact durable start that remains in flight.
88        attempt: NodeAttemptStartHead,
89    },
90    /// The latest physical attempt failed without automatic retry authority.
91    Failed {
92        /// Canonical activation derived from the checkpoint.
93        activation: NodeActivation,
94        /// Public-safe durable failure evidence.
95        failure: Failure,
96    },
97    /// No further physical start is allowed for this logical activation.
98    Exhausted {
99        /// Canonical activation derived from the checkpoint.
100        activation: NodeActivation,
101        /// Most recent durable physical start.
102        attempt: NodeAttemptStartHead,
103        /// Latest failure evidence when exhaustion followed a safe failure.
104        failure: Option<Failure>,
105    },
106}
107
108impl RecoveryNode {
109    /// Returns the closed scheduler classification.
110    #[must_use]
111    pub const fn kind(&self) -> RecoveryNodeKind {
112        match self {
113            Self::Completed { .. } => RecoveryNodeKind::Completed,
114            Self::Dispatchable { .. } => RecoveryNodeKind::Dispatchable,
115            Self::Deferred { .. } => RecoveryNodeKind::Deferred,
116            Self::InFlight { .. } => RecoveryNodeKind::InFlight,
117            Self::Failed { .. } => RecoveryNodeKind::Failed,
118            Self::Exhausted { .. } => RecoveryNodeKind::Exhausted,
119        }
120    }
121
122    /// Returns the canonical logical activation.
123    #[must_use]
124    pub const fn activation(&self) -> &NodeActivation {
125        match self {
126            Self::Completed { activation, .. }
127            | Self::Dispatchable { activation, .. }
128            | Self::Deferred { activation, .. }
129            | Self::InFlight { activation, .. }
130            | Self::Failed { activation, .. }
131            | Self::Exhausted { activation, .. } => activation,
132        }
133    }
134
135    /// Returns the dispatch reason when a new start is permitted.
136    #[must_use]
137    pub const fn dispatch_reason(&self) -> Option<NodeDispatchReason> {
138        match self {
139            Self::Dispatchable { reason, .. } => Some(*reason),
140            _ => None,
141        }
142    }
143
144    /// Returns the immutable completed result, if any.
145    #[must_use]
146    pub const fn result(&self) -> Option<&PendingNodeResultHead> {
147        match self {
148            Self::Completed { result, .. } => Some(result),
149            _ => None,
150        }
151    }
152
153    /// Returns the inclusive retry instant for a deferred node, if any.
154    #[must_use]
155    pub const fn not_before(&self) -> Option<Timestamp> {
156        match self {
157            Self::Deferred { not_before, .. } => Some(*not_before),
158            _ => None,
159        }
160    }
161
162    /// Returns the same-fence unfinished start, if any.
163    #[must_use]
164    pub const fn in_flight_attempt(&self) -> Option<&NodeAttemptStartHead> {
165        match self {
166            Self::InFlight { attempt, .. } => Some(attempt),
167            _ => None,
168        }
169    }
170
171    /// Returns terminal public-safe node failure evidence, if any.
172    #[must_use]
173    pub const fn failure(&self) -> Option<&Failure> {
174        match self {
175            Self::Failed { failure, .. } => Some(failure),
176            Self::Exhausted { failure, .. } => failure.as_ref(),
177            _ => None,
178        }
179    }
180
181    /// Returns the final physical start when the hard attempt limit was
182    /// reached, if applicable.
183    #[must_use]
184    pub const fn exhausted_attempt(&self) -> Option<&NodeAttemptStartHead> {
185        match self {
186            Self::Exhausted { attempt, .. } => Some(attempt),
187            _ => None,
188        }
189    }
190}
191
192/// Immutable deterministic plan for the exact ready set of one checkpoint.
193#[derive(Clone, Debug)]
194pub struct ReadyNodeRecoveryPlan {
195    checkpoint: Checkpoint,
196    fence: RunFence,
197    journal_head: JournalHead,
198    observed_at: Timestamp,
199    nodes: Box<[RecoveryNode]>,
200}
201
202impl ReadyNodeRecoveryPlan {
203    /// Returns the fully verified immutable state snapshot shared by every node.
204    #[must_use]
205    pub const fn checkpoint(&self) -> &Checkpoint {
206        &self.checkpoint
207    }
208
209    /// Returns the exact worker ownership used to classify attempt histories.
210    #[must_use]
211    pub const fn fence(&self) -> &RunFence {
212        &self.fence
213    }
214
215    /// Returns the exact verified run-journal observation behind this plan.
216    #[must_use]
217    pub const fn journal_head(&self) -> &JournalHead {
218        &self.journal_head
219    }
220
221    /// Returns the database timestamp used for retry classification.
222    #[must_use]
223    pub const fn observed_at(&self) -> Timestamp {
224        self.observed_at
225    }
226
227    /// Returns every ready node in deterministic ascending `NodeId` order.
228    #[must_use]
229    pub const fn nodes(&self) -> &[RecoveryNode] {
230        &self.nodes
231    }
232
233    /// Returns whether every ready activation already has an immutable result.
234    #[must_use]
235    pub fn is_barrier_ready(&self) -> bool {
236        !self.nodes.is_empty()
237            && self
238                .nodes
239                .iter()
240                .all(|node| node.kind() == RecoveryNodeKind::Completed)
241    }
242
243    /// Builds the exact compact result set when the checkpoint can enter its
244    /// barrier, or returns `None` while any activation remains unsettled.
245    ///
246    /// # Errors
247    ///
248    /// Returns [`BarrierResultHeadsError`] only if an internal invariant is
249    /// violated while materializing the already validated canonical set.
250    pub fn barrier_result_heads(
251        &self,
252    ) -> Result<Option<BarrierResultHeads>, BarrierResultHeadsError> {
253        if !self.is_barrier_ready() {
254            return Ok(None);
255        }
256        let results = self.nodes.iter().filter_map(RecoveryNode::result).cloned();
257        BarrierResultHeads::try_new(results).map(Some)
258    }
259
260    /// Returns the earliest durable retry instant when at least one node is
261    /// deferred.
262    #[must_use]
263    pub fn earliest_deferred_at(&self) -> Option<Timestamp> {
264        self.nodes.iter().filter_map(RecoveryNode::not_before).min()
265    }
266}
267
268#[derive(Clone, Debug)]
269struct RecoveryEntry {
270    activation: NodeActivation,
271    result: Option<PendingNodeResultHead>,
272    attempts: NodeAttemptHistoryVerifier,
273    attempt_count: usize,
274}
275
276/// Incremental, bounded verifier for one ready-node recovery snapshot.
277///
278/// Callers may stream large durable records through this builder. It retains
279/// one compact result head, the last full attempt, and at most 64 physical
280/// attempt identities per ready node. Combined with the checkpoint's 1024-node
281/// ceiling, both decoded-record and identity-set memory have a hard bound.
282#[derive(Clone, Debug)]
283pub struct ReadyNodeRecoveryPlanner {
284    checkpoint: Checkpoint,
285    fence: RunFence,
286    entries: BTreeMap<NodeId, RecoveryEntry>,
287}
288
289impl ReadyNodeRecoveryPlanner {
290    /// Hard physical-attempt ceiling for one logical activation.
291    ///
292    /// Runtime policy should normally stop much earlier. This defense-in-depth
293    /// bound prevents corrupt or adversarial durable history from turning
294    /// recovery verification into unbounded memory growth.
295    pub const MAX_ATTEMPTS_PER_NODE: usize = 64;
296
297    /// Seeds an exact canonical activation for every checkpoint-ready root node.
298    ///
299    /// # Errors
300    ///
301    /// Returns [`ReadyNodeRecoveryError`] when the fence crosses checkpoint
302    /// scope or deterministic activation construction fails.
303    pub fn new(checkpoint: Checkpoint, fence: RunFence) -> Result<Self, ReadyNodeRecoveryError> {
304        if fence.tenant_id() != checkpoint.tenant_id() {
305            return Err(ReadyNodeRecoveryError::FenceTenantMismatch);
306        }
307        if fence.run_id() != checkpoint.run_id() {
308            return Err(ReadyNodeRecoveryError::FenceRunMismatch);
309        }
310        let mut entries = BTreeMap::new();
311        for node_id in checkpoint.ready_nodes().iter().cloned() {
312            let activation = NodeActivation::for_ready_root(&checkpoint, node_id.clone())
313                .map_err(ReadyNodeRecoveryError::activation)?;
314            entries.insert(
315                node_id,
316                RecoveryEntry {
317                    activation,
318                    result: None,
319                    attempts: NodeAttemptHistoryVerifier::new(),
320                    attempt_count: 0,
321                },
322            );
323        }
324        Ok(Self {
325            checkpoint,
326            fence,
327            entries,
328        })
329    }
330
331    /// Observes one fully verified immutable pending result.
332    ///
333    /// # Errors
334    ///
335    /// Returns [`ReadyNodeRecoveryError::UnexpectedResult`] for an activation
336    /// outside the exact derived ready set or
337    /// [`ReadyNodeRecoveryError::DuplicateResult`] when a stream repeats one
338    /// logical activation.
339    pub fn observe_result(
340        &mut self,
341        result: &PendingNodeResult,
342    ) -> Result<(), ReadyNodeRecoveryError> {
343        let activation = result.intent().activation();
344        let Some(entry) = self.entries.get_mut(activation.node_id()) else {
345            return Err(ReadyNodeRecoveryError::UnexpectedResult {
346                node_id: activation.node_id().clone(),
347            });
348        };
349        if activation != &entry.activation {
350            return Err(ReadyNodeRecoveryError::UnexpectedResult {
351                node_id: activation.node_id().clone(),
352            });
353        }
354        if entry.result.is_some() {
355            return Err(ReadyNodeRecoveryError::DuplicateResult {
356                node_id: activation.node_id().clone(),
357            });
358        }
359        entry.result = Some(result.head());
360        Ok(())
361    }
362
363    /// Observes the next ascending physical attempt for one activation.
364    ///
365    /// # Errors
366    ///
367    /// Returns [`ReadyNodeRecoveryError::UnexpectedAttempt`] when the attempt
368    /// does not match the exact canonical activation, or wraps a complete
369    /// physical-history invariant failure.
370    pub fn observe_attempt(&mut self, attempt: &NodeAttempt) -> Result<(), ReadyNodeRecoveryError> {
371        let activation = attempt.start().activation();
372        let Some(entry) = self.entries.get_mut(activation.node_id()) else {
373            return Err(ReadyNodeRecoveryError::UnexpectedAttempt {
374                node_id: activation.node_id().clone(),
375            });
376        };
377        if activation != &entry.activation {
378            return Err(ReadyNodeRecoveryError::UnexpectedAttempt {
379                node_id: activation.node_id().clone(),
380            });
381        }
382        if entry.attempt_count >= Self::MAX_ATTEMPTS_PER_NODE {
383            return Err(ReadyNodeRecoveryError::AttemptLimitExceeded {
384                node_id: activation.node_id().clone(),
385                maximum: Self::MAX_ATTEMPTS_PER_NODE,
386            });
387        }
388        entry.attempts.verify_next(attempt).map_err(|source| {
389            ReadyNodeRecoveryError::AttemptHistory {
390                node_id: activation.node_id().clone(),
391                source,
392            }
393        })?;
394        entry.attempt_count += 1;
395        Ok(())
396    }
397
398    /// Returns every canonical ready-node activation in deterministic order.
399    ///
400    /// Providers use this bounded list to verify complete physical histories
401    /// even for completed siblings. That additional pass detects impossible
402    /// attempts before or after an otherwise valid immutable result.
403    #[must_use]
404    pub fn activations(&self) -> Vec<NodeActivation> {
405        self.entries
406            .values()
407            .map(|entry| entry.activation.clone())
408            .collect()
409    }
410
411    /// Finalizes every node decision at one database-observed instant.
412    ///
413    /// # Errors
414    ///
415    /// Returns [`ReadyNodeRecoveryError`] for a current fence that contradicts
416    /// durable attempt history, a success missing its result, a mismatched
417    /// success/result pair, unsupported retry evidence, or timestamp overflow.
418    pub fn finish(
419        self,
420        journal_head: JournalHead,
421        observed_at: Timestamp,
422    ) -> Result<ReadyNodeRecoveryPlan, ReadyNodeRecoveryError> {
423        validate_observation(&self, &journal_head, observed_at)?;
424        let mut nodes = Vec::with_capacity(self.entries.len());
425        for (node_id, entry) in self.entries {
426            nodes.push(classify_entry(node_id, entry, &self.fence, observed_at)?);
427        }
428        Ok(ReadyNodeRecoveryPlan {
429            checkpoint: self.checkpoint,
430            fence: self.fence,
431            journal_head,
432            observed_at,
433            nodes: nodes.into_boxed_slice(),
434        })
435    }
436}
437
438/// Invalid or contradictory inputs to deterministic ready-node recovery.
439#[derive(Clone, Debug, Eq, Error, PartialEq)]
440#[non_exhaustive]
441pub enum ReadyNodeRecoveryError {
442    /// The live worker fence crossed the checkpoint tenant boundary.
443    #[error("ready-node recovery fence crosses the checkpoint tenant boundary")]
444    FenceTenantMismatch,
445    /// The live worker fence named another run.
446    #[error("ready-node recovery fence does not belong to the checkpoint run")]
447    FenceRunMismatch,
448    /// Canonical activation derivation failed.
449    #[error("ready-node activation derivation failed: {source}")]
450    Activation {
451        /// Exact activation construction failure.
452        #[source]
453        source: NodeActivationError,
454    },
455    /// A pending result was outside the exact canonical ready-activation set.
456    #[error("pending result for node {node_id:?} is not part of the recovery ready set")]
457    UnexpectedResult {
458        /// Rejected node identity.
459        node_id: NodeId,
460    },
461    /// A streamed recovery result repeated one logical activation.
462    #[error("pending result for node {node_id:?} was observed more than once")]
463    DuplicateResult {
464        /// Repeated node identity.
465        node_id: NodeId,
466    },
467    /// A physical attempt was outside the exact canonical activation set.
468    #[error("physical attempt for node {node_id:?} is not part of the recovery ready set")]
469    UnexpectedAttempt {
470        /// Rejected node identity.
471        node_id: NodeId,
472    },
473    /// One activation's physical-attempt history was contradictory.
474    #[error("physical attempt history for node {node_id:?} is invalid: {source}")]
475    AttemptHistory {
476        /// Affected node identity.
477        node_id: NodeId,
478        /// Exact history invariant failure.
479        #[source]
480        source: NodeAttemptHistoryError,
481    },
482    /// One logical activation exceeded the hard recovery history ceiling.
483    #[error("physical attempt history for node {node_id:?} exceeds {maximum} records")]
484    AttemptLimitExceeded {
485        /// Affected node identity.
486        node_id: NodeId,
487        /// Closed implementation ceiling.
488        maximum: usize,
489    },
490    /// Durable history contains a worker epoch newer than the claimed fence.
491    #[error("physical attempt history for node {node_id:?} is newer than the recovery fence")]
492    CurrentFenceBehindHistory {
493        /// Affected node identity.
494        node_id: NodeId,
495    },
496    /// The same fencing epoch names a different worker attempt.
497    #[error("physical attempt history for node {node_id:?} conflicts with the recovery fence")]
498    CurrentFenceConflict {
499        /// Affected node identity.
500        node_id: NodeId,
501    },
502    /// A higher worker epoch improperly reused an earlier worker attempt ID.
503    #[error("recovery fence reused an earlier worker attempt for node {node_id:?}")]
504    CurrentFenceAttemptReused {
505        /// Affected node identity.
506        node_id: NodeId,
507    },
508    /// A successful attempt exists without its required immutable result.
509    #[error("successful physical attempt for node {node_id:?} has no pending result")]
510    SucceededWithoutResult {
511        /// Affected node identity.
512        node_id: NodeId,
513    },
514    /// The successful attempt and observed immutable result disagree.
515    #[error("successful physical attempt for node {node_id:?} references another result")]
516    ResultAttemptMismatch {
517        /// Affected node identity.
518        node_id: NodeId,
519    },
520    /// Node-attempt failure contained a retry class forbidden by its contract.
521    #[error("physical node failure for node {node_id:?} has unsupported retry advice")]
522    UnsupportedRetryAdvice {
523        /// Affected node identity.
524        node_id: NodeId,
525    },
526    /// Safe-after arithmetic exceeded the canonical timestamp range.
527    #[error("physical node retry time for node {node_id:?} exceeds the timestamp range")]
528    RetryNotBeforeOutOfRange {
529        /// Affected node identity.
530        node_id: NodeId,
531    },
532    /// The final journal observation crossed the checkpoint tenant boundary.
533    #[error("ready-node recovery journal observation crosses the checkpoint tenant boundary")]
534    ObservationTenantMismatch,
535    /// The final journal observation named another run.
536    #[error("ready-node recovery journal observation does not belong to the checkpoint run")]
537    ObservationRunMismatch,
538    /// The final journal observation preceded the checkpoint anchor.
539    #[error("ready-node recovery journal observation precedes the checkpoint")]
540    ObservationBeforeCheckpoint,
541    /// The final journal observation preceded a streamed result or attempt.
542    #[error("ready-node recovery journal observation precedes durable node evidence")]
543    ObservationBeforeEvidence,
544    /// The database clock observation preceded the verified journal head.
545    #[error("ready-node recovery database clock precedes its journal observation")]
546    ObservationClockRegression,
547}
548
549impl ReadyNodeRecoveryError {
550    const fn activation(source: NodeActivationError) -> Self {
551        Self::Activation { source }
552    }
553}
554
555fn classify_entry(
556    node_id: NodeId,
557    entry: RecoveryEntry,
558    current_fence: &RunFence,
559    observed_at: Timestamp,
560) -> Result<RecoveryNode, ReadyNodeRecoveryError> {
561    let RecoveryEntry {
562        activation,
563        result,
564        attempts,
565        attempt_count,
566    } = entry;
567    let latest = attempts.last();
568
569    if let Some(result) = result {
570        validate_current_fence(&node_id, result.fence(), current_fence)?;
571        if let Some(attempt) = latest {
572            let Some(completion) = attempt.completion() else {
573                return Err(ReadyNodeRecoveryError::ResultAttemptMismatch { node_id });
574            };
575            if completion.outcome().result() != Some(&result) {
576                return Err(ReadyNodeRecoveryError::ResultAttemptMismatch { node_id });
577            }
578        }
579        return Ok(RecoveryNode::Completed { activation, result });
580    }
581
582    let Some(attempt) = latest else {
583        return Ok(RecoveryNode::Dispatchable {
584            activation,
585            reason: NodeDispatchReason::FirstAttempt,
586        });
587    };
588    validate_current_fence(&node_id, attempt.start().fence(), current_fence)?;
589
590    match attempt.status() {
591        NodeAttemptStatus::Executing => {
592            if attempt.start().fence() == current_fence {
593                Ok(RecoveryNode::InFlight {
594                    activation,
595                    attempt: attempt.start().head(),
596                })
597            } else if attempt_count >= ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE {
598                Ok(RecoveryNode::Exhausted {
599                    activation,
600                    attempt: attempt.start().head(),
601                    failure: None,
602                })
603            } else {
604                Ok(RecoveryNode::Dispatchable {
605                    activation,
606                    reason: NodeDispatchReason::SupersededAttempt,
607                })
608            }
609        }
610        NodeAttemptStatus::Succeeded => {
611            Err(ReadyNodeRecoveryError::SucceededWithoutResult { node_id })
612        }
613        NodeAttemptStatus::Failed => {
614            let completion = attempt.completion().ok_or_else(|| {
615                ReadyNodeRecoveryError::SucceededWithoutResult {
616                    node_id: node_id.clone(),
617                }
618            })?;
619            let NodeAttemptOutcome::Failed { failure } = completion.outcome() else {
620                return Err(ReadyNodeRecoveryError::SucceededWithoutResult { node_id });
621            };
622            match failure.retry_advice() {
623                RetryAdvice::Never => Ok(RecoveryNode::Failed {
624                    activation,
625                    failure: failure.clone(),
626                }),
627                RetryAdvice::SafeAfter { delay } => {
628                    if attempt_count >= ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE {
629                        return Ok(RecoveryNode::Exhausted {
630                            activation,
631                            attempt: attempt.start().head(),
632                            failure: Some(failure.clone()),
633                        });
634                    }
635                    let not_before =
636                        retry_not_before(completion.journal_head().recorded_at(), delay.as_i64())
637                            .ok_or_else(|| ReadyNodeRecoveryError::RetryNotBeforeOutOfRange {
638                            node_id: node_id.clone(),
639                        })?;
640                    if observed_at >= not_before {
641                        Ok(RecoveryNode::Dispatchable {
642                            activation,
643                            reason: NodeDispatchReason::SafeRetry,
644                        })
645                    } else {
646                        Ok(RecoveryNode::Deferred {
647                            activation,
648                            not_before,
649                        })
650                    }
651                }
652                RetryAdvice::ReconcileFirst => {
653                    Err(ReadyNodeRecoveryError::UnsupportedRetryAdvice { node_id })
654                }
655            }
656        }
657    }
658}
659
660fn validate_observation(
661    planner: &ReadyNodeRecoveryPlanner,
662    journal_head: &JournalHead,
663    observed_at: Timestamp,
664) -> Result<(), ReadyNodeRecoveryError> {
665    if journal_head.tenant_id() != planner.checkpoint.tenant_id() {
666        return Err(ReadyNodeRecoveryError::ObservationTenantMismatch);
667    }
668    if journal_head.run_id() != planner.checkpoint.run_id() {
669        return Err(ReadyNodeRecoveryError::ObservationRunMismatch);
670    }
671    let checkpoint_head = planner.checkpoint.journal_head();
672    if journal_head.sequence() < checkpoint_head.sequence()
673        || journal_head.recorded_at() < checkpoint_head.recorded_at()
674    {
675        return Err(ReadyNodeRecoveryError::ObservationBeforeCheckpoint);
676    }
677    if observed_at < journal_head.recorded_at() {
678        return Err(ReadyNodeRecoveryError::ObservationClockRegression);
679    }
680    for entry in planner.entries.values() {
681        let result_head = entry
682            .result
683            .as_ref()
684            .map(PendingNodeResultHead::journal_head);
685        let attempt_head = entry.attempts.last().map(|attempt| {
686            attempt.completion().map_or_else(
687                || attempt.start().journal_head(),
688                |value| value.journal_head(),
689            )
690        });
691        if result_head.into_iter().chain(attempt_head).any(|evidence| {
692            evidence.sequence() > journal_head.sequence()
693                || evidence.recorded_at() > journal_head.recorded_at()
694        }) {
695            return Err(ReadyNodeRecoveryError::ObservationBeforeEvidence);
696        }
697    }
698    Ok(())
699}
700
701fn validate_current_fence(
702    node_id: &NodeId,
703    historical: &RunFence,
704    current: &RunFence,
705) -> Result<(), ReadyNodeRecoveryError> {
706    if historical.epoch() > current.epoch() {
707        return Err(ReadyNodeRecoveryError::CurrentFenceBehindHistory {
708            node_id: node_id.clone(),
709        });
710    }
711    if historical.epoch() == current.epoch() && historical.attempt_id() != current.attempt_id() {
712        return Err(ReadyNodeRecoveryError::CurrentFenceConflict {
713            node_id: node_id.clone(),
714        });
715    }
716    if historical.epoch() < current.epoch() && historical.attempt_id() == current.attempt_id() {
717        return Err(ReadyNodeRecoveryError::CurrentFenceAttemptReused {
718            node_id: node_id.clone(),
719        });
720    }
721    Ok(())
722}
723
724fn retry_not_before(failed_at: Timestamp, delay_millis: i64) -> Option<Timestamp> {
725    let micros = i128::from(failed_at.unix_micros())
726        .checked_add(i128::from(delay_millis).checked_mul(1_000)?)?;
727    let micros = i64::try_from(micros).ok()?;
728    Timestamp::from_unix_micros(micros).ok()
729}
730
731#[cfg(test)]
732mod tests {
733    use proptest::prelude::*;
734    use serde_json::from_value;
735
736    use super::*;
737    use crate::{
738        AttemptId, BudgetUsage, CheckpointId, CheckpointWrite, Digest, DurationMillis, EventId,
739        FailureCategory, FailureCode, FailureId, FailureMessage, FailureOrigin, FencingEpoch,
740        GraphNamespace, JournalHead, JournalSequence, NodeAttemptCompletion, NodeControl,
741        NodeInvocationBindings, NodeStateChange, PendingNodeResultIntent, ReadyNodes, RunId,
742        TenantId,
743    };
744
745    fn checkpoint() -> Checkpoint {
746        let fixture: serde_json::Value =
747            serde_json::from_str(include_str!("../tests/fixtures/core-checkpoint-v1.json"))
748                .unwrap();
749        from_value(fixture["checkpoints"][0].clone()).unwrap()
750    }
751
752    fn checkpoint_with_nodes(count: usize) -> Checkpoint {
753        let template = checkpoint();
754        let tenant_id = template.tenant_id().clone();
755        let run_id = RunId::generate();
756        let ready_nodes = ReadyNodes::try_new(
757            (0..count).map(|index| NodeId::new(format!("node-{index:04}")).unwrap()),
758        )
759        .unwrap();
760        let write = CheckpointWrite::initial(
761            tenant_id.clone(),
762            run_id,
763            CheckpointId::generate(),
764            template.graph().clone(),
765            template.state().clone(),
766            ready_nodes,
767        )
768        .unwrap();
769        let journal_head = JournalHead::new(
770            tenant_id,
771            run_id,
772            JournalSequence::FIRST,
773            EventId::generate(),
774            template.journal_head().recorded_at(),
775            Digest::sha256(b"property checkpoint journal"),
776        );
777        Checkpoint::commit(write, journal_head).unwrap()
778    }
779
780    fn node(name: &str) -> NodeId {
781        NodeId::new(name).unwrap()
782    }
783
784    fn activation(checkpoint: &Checkpoint, name: &str) -> NodeActivation {
785        NodeActivation::for_ready_root(checkpoint, node(name)).unwrap()
786    }
787
788    fn fence(checkpoint: &Checkpoint, epoch: u64) -> RunFence {
789        RunFence::new(
790            checkpoint.tenant_id().clone(),
791            checkpoint.run_id(),
792            AttemptId::generate(),
793            FencingEpoch::new(epoch).unwrap(),
794        )
795    }
796
797    fn journal(checkpoint: &Checkpoint, offset: u64) -> JournalHead {
798        let base = checkpoint.journal_head();
799        let sequence = JournalSequence::new(base.sequence().get() + offset).unwrap();
800        let recorded_at = Timestamp::from_unix_micros(
801            base.recorded_at().unix_micros() + i64::try_from(offset).unwrap() * 1_000_000,
802        )
803        .unwrap();
804        JournalHead::new(
805            checkpoint.tenant_id().clone(),
806            checkpoint.run_id(),
807            sequence,
808            EventId::generate(),
809            recorded_at,
810            Digest::sha256(format!("recovery journal {offset}")),
811        )
812    }
813
814    fn executing_attempt(
815        checkpoint: &Checkpoint,
816        name: &str,
817        owner: RunFence,
818        offset: u64,
819    ) -> NodeAttempt {
820        let start = crate::NodeAttemptStart::new(
821            activation(checkpoint, name),
822            AttemptId::generate(),
823            owner,
824            journal(checkpoint, offset),
825        )
826        .unwrap();
827        NodeAttempt::executing(start)
828    }
829
830    fn result(
831        checkpoint: &Checkpoint,
832        name: &str,
833        owner: RunFence,
834        offset: u64,
835    ) -> PendingNodeResult {
836        let intent = PendingNodeResultIntent::new(
837            activation(checkpoint, name),
838            NodeStateChange::Unchanged,
839            NodeControl::Continue,
840            NodeInvocationBindings::empty(),
841        )
842        .unwrap();
843        PendingNodeResult::commit(intent, owner, journal(checkpoint, offset)).unwrap()
844    }
845
846    fn succeeded_attempt(
847        checkpoint: &Checkpoint,
848        name: &str,
849        owner: RunFence,
850        start_offset: u64,
851        result_offset: u64,
852    ) -> (NodeAttempt, PendingNodeResult) {
853        let start = crate::NodeAttemptStart::new(
854            activation(checkpoint, name),
855            AttemptId::generate(),
856            owner.clone(),
857            journal(checkpoint, start_offset),
858        )
859        .unwrap();
860        let result = result(checkpoint, name, owner, result_offset);
861        let completion =
862            NodeAttemptCompletion::succeed(&start, result.head(), BudgetUsage::zero()).unwrap();
863        (
864            NodeAttempt::restore(start, Some(completion)).unwrap(),
865            result,
866        )
867    }
868
869    fn failed_attempt(
870        checkpoint: &Checkpoint,
871        name: &str,
872        owner: RunFence,
873        start_offset: u64,
874        completion_offset: u64,
875        advice: RetryAdvice,
876    ) -> NodeAttempt {
877        let start = crate::NodeAttemptStart::new(
878            activation(checkpoint, name),
879            AttemptId::generate(),
880            owner,
881            journal(checkpoint, start_offset),
882        )
883        .unwrap();
884        let completion_journal = journal(checkpoint, completion_offset);
885        let failure = Failure::new(
886            FailureId::generate(),
887            FailureCategory::DependencyUnavailable,
888            FailureCode::new("node.test_failure").unwrap(),
889            FailureOrigin::new("runtime.test").unwrap(),
890            FailureMessage::new("The deterministic test node failed.").unwrap(),
891            advice,
892        )
893        .unwrap()
894        .with_caused_by_event(completion_journal.event_id());
895        let completion =
896            NodeAttemptCompletion::fail(&start, failure, BudgetUsage::zero(), completion_journal)
897                .unwrap();
898        NodeAttempt::restore(start, Some(completion)).unwrap()
899    }
900
901    fn decision<'a>(plan: &'a ReadyNodeRecoveryPlan, name: &str) -> &'a RecoveryNode {
902        plan.nodes()
903            .iter()
904            .find(|decision| decision.activation().node_id().as_str() == name)
905            .unwrap()
906    }
907
908    #[test]
909    fn pristine_ready_set_is_dispatchable_in_canonical_order() {
910        let checkpoint = checkpoint();
911        let owner = fence(&checkpoint, 1);
912        let journal_head = journal(&checkpoint, 10);
913        let observed_at = journal_head.recorded_at();
914        let plan = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone())
915            .unwrap()
916            .finish(journal_head.clone(), observed_at)
917            .unwrap();
918
919        assert_eq!(plan.checkpoint(), &checkpoint);
920        assert_eq!(plan.fence(), &owner);
921        assert_eq!(plan.journal_head(), &journal_head);
922        assert_eq!(plan.observed_at(), observed_at);
923        assert_eq!(
924            plan.nodes()
925                .iter()
926                .map(|decision| decision.activation().node_id().as_str())
927                .collect::<Vec<_>>(),
928            ["authorize", "reserve-stock"]
929        );
930        assert!(plan.nodes().iter().all(|decision| {
931            decision.kind() == RecoveryNodeKind::Dispatchable
932                && decision.dispatch_reason() == Some(NodeDispatchReason::FirstAttempt)
933        }));
934        assert!(!plan.is_barrier_ready());
935        assert!(plan.barrier_result_heads().unwrap().is_none());
936    }
937
938    #[test]
939    fn committed_siblings_are_reused_independent_of_observation_order() {
940        let checkpoint = checkpoint();
941        let owner = fence(&checkpoint, 1);
942        let (authorize_attempt, authorize) =
943            succeeded_attempt(&checkpoint, "authorize", owner.clone(), 1, 2);
944        let (reserve_attempt, reserve) =
945            succeeded_attempt(&checkpoint, "reserve-stock", owner.clone(), 3, 4);
946        let observation = journal(&checkpoint, 10);
947
948        let mut forward = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
949        forward.observe_result(&authorize).unwrap();
950        forward.observe_result(&reserve).unwrap();
951        forward.observe_attempt(&reserve_attempt).unwrap();
952        forward.observe_attempt(&authorize_attempt).unwrap();
953        let forward = forward
954            .finish(observation.clone(), observation.recorded_at())
955            .unwrap();
956
957        let mut reverse = ReadyNodeRecoveryPlanner::new(checkpoint, owner).unwrap();
958        reverse.observe_result(&reserve).unwrap();
959        reverse.observe_result(&authorize).unwrap();
960        let reverse = reverse
961            .finish(observation.clone(), observation.recorded_at())
962            .unwrap();
963
964        assert!(forward.is_barrier_ready());
965        assert!(reverse.is_barrier_ready());
966        let forward_heads = forward.barrier_result_heads().unwrap().unwrap();
967        let reverse_heads = reverse.barrier_result_heads().unwrap().unwrap();
968        assert_eq!(forward_heads, reverse_heads);
969        assert_eq!(
970            forward_heads
971                .iter()
972                .map(|head| head.activation().node_id().as_str())
973                .collect::<Vec<_>>(),
974            ["authorize", "reserve-stock"]
975        );
976    }
977
978    #[test]
979    fn unfinished_attempt_requires_higher_fence_and_same_fence_stays_in_flight() {
980        let checkpoint = checkpoint();
981        let old_owner = fence(&checkpoint, 1);
982        let attempt = executing_attempt(&checkpoint, "authorize", old_owner.clone(), 1);
983
984        let mut same =
985            ReadyNodeRecoveryPlanner::new(checkpoint.clone(), old_owner.clone()).unwrap();
986        same.observe_attempt(&attempt).unwrap();
987        let observation = journal(&checkpoint, 10);
988        let same = same
989            .finish(observation.clone(), observation.recorded_at())
990            .unwrap();
991        assert_eq!(
992            decision(&same, "authorize").kind(),
993            RecoveryNodeKind::InFlight
994        );
995
996        let successor = fence(&checkpoint, 2);
997        let mut recovered = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), successor).unwrap();
998        recovered.observe_attempt(&attempt).unwrap();
999        let recovered = recovered
1000            .finish(observation.clone(), observation.recorded_at())
1001            .unwrap();
1002        assert_eq!(
1003            decision(&recovered, "authorize").dispatch_reason(),
1004            Some(NodeDispatchReason::SupersededAttempt)
1005        );
1006
1007        let stale_owner = fence(&checkpoint, 1);
1008        let newer_attempt = executing_attempt(&checkpoint, "authorize", fence(&checkpoint, 2), 1);
1009        let mut stale = ReadyNodeRecoveryPlanner::new(checkpoint, stale_owner).unwrap();
1010        stale.observe_attempt(&newer_attempt).unwrap();
1011        assert!(matches!(
1012            stale.finish(observation.clone(), observation.recorded_at()),
1013            Err(ReadyNodeRecoveryError::CurrentFenceBehindHistory { .. })
1014        ));
1015    }
1016
1017    #[test]
1018    fn safe_retry_uses_inclusive_database_time_and_never_failure_blocks() {
1019        let checkpoint = checkpoint();
1020        let owner = fence(&checkpoint, 1);
1021        let retry = failed_attempt(
1022            &checkpoint,
1023            "authorize",
1024            owner.clone(),
1025            1,
1026            2,
1027            RetryAdvice::SafeAfter {
1028                delay: DurationMillis::new(5_000).unwrap(),
1029            },
1030        );
1031        let failed_at = retry.completion().unwrap().journal_head().recorded_at();
1032        let retry_observation = retry.completion().unwrap().journal_head().clone();
1033        let not_before = Timestamp::from_unix_micros(failed_at.unix_micros() + 5_000_000).unwrap();
1034
1035        let mut early = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1036        early.observe_attempt(&retry).unwrap();
1037        let early = early
1038            .finish(
1039                retry_observation.clone(),
1040                Timestamp::from_unix_micros(not_before.unix_micros() - 1).unwrap(),
1041            )
1042            .unwrap();
1043        assert_eq!(
1044            decision(&early, "authorize").kind(),
1045            RecoveryNodeKind::Deferred
1046        );
1047        assert_eq!(decision(&early, "authorize").not_before(), Some(not_before));
1048        assert_eq!(early.earliest_deferred_at(), Some(not_before));
1049
1050        let mut due = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1051        due.observe_attempt(&retry).unwrap();
1052        let due = due.finish(retry_observation, not_before).unwrap();
1053        assert_eq!(
1054            decision(&due, "authorize").dispatch_reason(),
1055            Some(NodeDispatchReason::SafeRetry)
1056        );
1057
1058        let terminal = failed_attempt(
1059            &checkpoint,
1060            "authorize",
1061            owner.clone(),
1062            3,
1063            4,
1064            RetryAdvice::Never,
1065        );
1066        let terminal_observation = terminal.completion().unwrap().journal_head().clone();
1067        let mut blocked = ReadyNodeRecoveryPlanner::new(checkpoint, owner).unwrap();
1068        blocked.observe_attempt(&terminal).unwrap();
1069        let blocked = blocked.finish(terminal_observation, not_before).unwrap();
1070        assert_eq!(
1071            decision(&blocked, "authorize").kind(),
1072            RecoveryNodeKind::Failed
1073        );
1074        assert!(decision(&blocked, "authorize").failure().is_some());
1075    }
1076
1077    #[test]
1078    fn activation_drift_and_success_without_result_fail_closed() {
1079        let checkpoint = checkpoint();
1080        let owner = fence(&checkpoint, 1);
1081        let drifted = NodeActivation::new(
1082            checkpoint.head(),
1083            GraphNamespace::root(),
1084            node("authorize"),
1085            Digest::sha256(b"drifted scheduler input"),
1086        );
1087        let drifted = PendingNodeResult::commit(
1088            PendingNodeResultIntent::new(
1089                drifted,
1090                NodeStateChange::Unchanged,
1091                NodeControl::Continue,
1092                NodeInvocationBindings::empty(),
1093            )
1094            .unwrap(),
1095            owner.clone(),
1096            journal(&checkpoint, 2),
1097        )
1098        .unwrap();
1099        let mut planner = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1100        assert!(matches!(
1101            planner.observe_result(&drifted),
1102            Err(ReadyNodeRecoveryError::UnexpectedResult { .. })
1103        ));
1104
1105        let (success, _) = succeeded_attempt(&checkpoint, "authorize", owner.clone(), 1, 2);
1106        let observation = journal(&checkpoint, 10);
1107        let observed_at = observation.recorded_at();
1108        let mut missing = ReadyNodeRecoveryPlanner::new(checkpoint, owner).unwrap();
1109        missing.observe_attempt(&success).unwrap();
1110        assert!(matches!(
1111            missing.finish(observation, observed_at),
1112            Err(ReadyNodeRecoveryError::SucceededWithoutResult { .. })
1113        ));
1114
1115        let mismatched_checkpoint = self::checkpoint();
1116        let owner = fence(&mismatched_checkpoint, 1);
1117        let durable_result = result(&mismatched_checkpoint, "authorize", owner.clone(), 4);
1118        let unrelated_failure = failed_attempt(
1119            &mismatched_checkpoint,
1120            "authorize",
1121            owner.clone(),
1122            1,
1123            2,
1124            RetryAdvice::Never,
1125        );
1126        let observation = journal(&mismatched_checkpoint, 10);
1127        let mut mismatched = ReadyNodeRecoveryPlanner::new(mismatched_checkpoint, owner).unwrap();
1128        mismatched.observe_result(&durable_result).unwrap();
1129        mismatched.observe_attempt(&unrelated_failure).unwrap();
1130        assert!(matches!(
1131            mismatched.finish(observation.clone(), observation.recorded_at()),
1132            Err(ReadyNodeRecoveryError::ResultAttemptMismatch { .. })
1133        ));
1134    }
1135
1136    #[test]
1137    fn completed_result_cannot_come_from_a_future_or_conflicting_fence() {
1138        let checkpoint = checkpoint();
1139        let old = result(&checkpoint, "authorize", fence(&checkpoint, 1), 2);
1140        let successor = fence(&checkpoint, 2);
1141        let observation = journal(&checkpoint, 10);
1142        let mut reusable = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), successor).unwrap();
1143        reusable.observe_result(&old).unwrap();
1144        assert_eq!(
1145            decision(
1146                &reusable
1147                    .finish(observation.clone(), observation.recorded_at())
1148                    .unwrap(),
1149                "authorize",
1150            )
1151            .kind(),
1152            RecoveryNodeKind::Completed
1153        );
1154
1155        let current = fence(&checkpoint, 1);
1156        let future = result(&checkpoint, "authorize", fence(&checkpoint, 2), 2);
1157        let mut future_plan =
1158            ReadyNodeRecoveryPlanner::new(checkpoint.clone(), current.clone()).unwrap();
1159        future_plan.observe_result(&future).unwrap();
1160        assert!(matches!(
1161            future_plan.finish(observation.clone(), observation.recorded_at()),
1162            Err(ReadyNodeRecoveryError::CurrentFenceBehindHistory { .. })
1163        ));
1164
1165        let conflict = result(&checkpoint, "authorize", fence(&checkpoint, 1), 2);
1166        let mut conflict_plan = ReadyNodeRecoveryPlanner::new(checkpoint, current).unwrap();
1167        conflict_plan.observe_result(&conflict).unwrap();
1168        assert!(matches!(
1169            conflict_plan.finish(observation.clone(), observation.recorded_at()),
1170            Err(ReadyNodeRecoveryError::CurrentFenceConflict { .. })
1171        ));
1172    }
1173
1174    #[test]
1175    fn crossed_scope_is_rejected_before_planning() {
1176        let checkpoint = checkpoint();
1177        let crossed_tenant = RunFence::new(
1178            TenantId::new("another-tenant").unwrap(),
1179            checkpoint.run_id(),
1180            AttemptId::generate(),
1181            FencingEpoch::new(1).unwrap(),
1182        );
1183        assert!(matches!(
1184            ReadyNodeRecoveryPlanner::new(checkpoint.clone(), crossed_tenant),
1185            Err(ReadyNodeRecoveryError::FenceTenantMismatch)
1186        ));
1187
1188        let crossed_run = RunFence::new(
1189            checkpoint.tenant_id().clone(),
1190            RunId::generate(),
1191            AttemptId::generate(),
1192            FencingEpoch::new(1).unwrap(),
1193        );
1194        assert!(matches!(
1195            ReadyNodeRecoveryPlanner::new(checkpoint, crossed_run),
1196            Err(ReadyNodeRecoveryError::FenceRunMismatch)
1197        ));
1198    }
1199
1200    #[test]
1201    fn final_observation_cannot_precede_evidence_or_database_clock() {
1202        let checkpoint = checkpoint();
1203        let owner = fence(&checkpoint, 1);
1204        let durable_result = result(&checkpoint, "authorize", owner.clone(), 2);
1205        let mut behind_evidence =
1206            ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1207        behind_evidence.observe_result(&durable_result).unwrap();
1208        assert!(matches!(
1209            behind_evidence.finish(
1210                checkpoint.journal_head().clone(),
1211                durable_result.journal_head().recorded_at(),
1212            ),
1213            Err(ReadyNodeRecoveryError::ObservationBeforeEvidence)
1214        ));
1215
1216        let observation = journal(&checkpoint, 10);
1217        let before_observation =
1218            Timestamp::from_unix_micros(observation.recorded_at().unix_micros() - 1).unwrap();
1219        assert!(matches!(
1220            ReadyNodeRecoveryPlanner::new(checkpoint, owner)
1221                .unwrap()
1222                .finish(observation, before_observation),
1223            Err(ReadyNodeRecoveryError::ObservationClockRegression)
1224        ));
1225    }
1226
1227    #[test]
1228    fn physical_attempt_history_has_a_hard_recovery_bound() {
1229        let checkpoint = checkpoint();
1230        let owner = fence(&checkpoint, 1);
1231        let mut planner = ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner.clone()).unwrap();
1232        for index in 0..ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE {
1233            let start_offset = u64::try_from(index * 2 + 1).unwrap();
1234            planner
1235                .observe_attempt(&failed_attempt(
1236                    &checkpoint,
1237                    "authorize",
1238                    owner.clone(),
1239                    start_offset,
1240                    start_offset + 1,
1241                    RetryAdvice::SafeAfter {
1242                        delay: DurationMillis::ZERO,
1243                    },
1244                ))
1245                .unwrap();
1246        }
1247        let observation = journal(&checkpoint, 200);
1248        let exhausted = planner
1249            .clone()
1250            .finish(observation.clone(), observation.recorded_at())
1251            .unwrap();
1252        assert_eq!(
1253            decision(&exhausted, "authorize").kind(),
1254            RecoveryNodeKind::Exhausted
1255        );
1256        assert!(
1257            decision(&exhausted, "authorize")
1258                .exhausted_attempt()
1259                .is_some()
1260        );
1261        let overflow_offset =
1262            u64::try_from(ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE * 2 + 1).unwrap();
1263        assert!(matches!(
1264            planner.observe_attempt(&failed_attempt(
1265                &checkpoint,
1266                "authorize",
1267                owner,
1268                overflow_offset,
1269                overflow_offset + 1,
1270                RetryAdvice::SafeAfter {
1271                    delay: DurationMillis::ZERO,
1272                },
1273            )),
1274            Err(ReadyNodeRecoveryError::AttemptLimitExceeded {
1275                maximum: ReadyNodeRecoveryPlanner::MAX_ATTEMPTS_PER_NODE,
1276                ..
1277            })
1278        ));
1279    }
1280
1281    proptest! {
1282        #![proptest_config(ProptestConfig::with_cases(64))]
1283
1284        #[test]
1285        fn arbitrary_result_observation_order_produces_canonical_barrier(
1286            (count, priorities) in (1_usize..=32).prop_flat_map(|count| {
1287                (Just(count), prop::collection::vec(any::<u16>(), count))
1288            }),
1289        ) {
1290            let checkpoint = checkpoint_with_nodes(count);
1291            let owner = fence(&checkpoint, 1);
1292            let results = checkpoint
1293                .ready_nodes()
1294                .iter()
1295                .enumerate()
1296                .map(|(index, node_id)| {
1297                    result(
1298                        &checkpoint,
1299                        node_id.as_str(),
1300                        owner.clone(),
1301                        u64::try_from(index + 1).unwrap(),
1302                    )
1303                })
1304                .collect::<Vec<_>>();
1305            let mut order = (0..count).collect::<Vec<_>>();
1306            order.sort_unstable_by_key(|index| (priorities[*index], *index));
1307
1308            let mut planner =
1309                ReadyNodeRecoveryPlanner::new(checkpoint.clone(), owner).unwrap();
1310            for index in order {
1311                planner.observe_result(&results[index]).unwrap();
1312            }
1313            let observation = journal(&checkpoint, u64::try_from(count + 1).unwrap());
1314            let plan = planner
1315                .finish(observation.clone(), observation.recorded_at())
1316                .unwrap();
1317            let expected = checkpoint
1318                .ready_nodes()
1319                .iter()
1320                .map(NodeId::as_str)
1321                .collect::<Vec<_>>();
1322            let actual = plan
1323                .nodes()
1324                .iter()
1325                .map(|decision| decision.activation().node_id().as_str())
1326                .collect::<Vec<_>>();
1327            prop_assert_eq!(actual, expected.clone());
1328            let barrier = plan.barrier_result_heads().unwrap().unwrap();
1329            let barrier_order = barrier
1330                .iter()
1331                .map(|head| head.activation().node_id().as_str())
1332                .collect::<Vec<_>>();
1333            prop_assert_eq!(barrier_order, expected);
1334        }
1335    }
1336}