1use std::{collections::BTreeSet, fmt};
13
14use schemars::{JsonSchema, Schema, SchemaGenerator, json_schema};
15use serde::{
16 Deserialize, Deserializer, Serialize,
17 de::{self, SeqAccess},
18};
19use thiserror::Error;
20
21use crate::{
22 Checkpoint, CheckpointHead, CheckpointWrite, Digest, GraphNamespace, NodeId,
23 PendingNodeResultHead, ReadyNodes,
24};
25
26const BARRIER_INTENT_DIGEST_DOMAIN: &[u8] = b"stateknot-checkpoint-barrier-intent-v1\0";
27
28#[derive(Clone, Debug, Eq, PartialEq)]
35pub struct BarrierResultHeads(Box<[PendingNodeResultHead]>);
36
37impl BarrierResultHeads {
38 pub const MAX_LEN: usize = ReadyNodes::MAX_LEN;
40
41 pub fn try_new<I>(values: I) -> Result<Self, BarrierResultHeadsError>
52 where
53 I: IntoIterator<Item = PendingNodeResultHead>,
54 {
55 let mut collected = Vec::new();
56 let mut identities = BTreeSet::new();
57 let mut base: Option<CheckpointHead> = None;
58 for value in values {
59 if collected.len() == Self::MAX_LEN {
60 return Err(BarrierResultHeadsError::TooMany {
61 maximum: Self::MAX_LEN,
62 actual: Self::MAX_LEN + 1,
63 });
64 }
65 let activation = value.activation();
66 if !activation.graph_namespace().is_root() {
67 return Err(BarrierResultHeadsError::NestedGraphNamespace {
68 namespace: activation.graph_namespace().clone(),
69 });
70 }
71 if let Some(expected) = &base {
72 if activation.base_checkpoint() != expected {
73 return Err(BarrierResultHeadsError::MixedBaseCheckpoints);
74 }
75 } else {
76 base = Some(activation.base_checkpoint().clone());
77 }
78 let identity = (
79 activation.graph_namespace().clone(),
80 activation.node_id().clone(),
81 );
82 if !identities.insert(identity.clone()) {
83 return Err(BarrierResultHeadsError::DuplicateActivation {
84 namespace: identity.0,
85 node_id: identity.1,
86 });
87 }
88 collected.push(value);
89 }
90 if collected.is_empty() {
91 return Err(BarrierResultHeadsError::Empty);
92 }
93 collected.sort_unstable_by(|left, right| {
94 let left = left.activation();
95 let right = right.activation();
96 (left.graph_namespace(), left.node_id())
97 .cmp(&(right.graph_namespace(), right.node_id()))
98 });
99 Ok(Self(collected.into_boxed_slice()))
100 }
101
102 #[must_use]
104 pub const fn len(&self) -> usize {
105 self.0.len()
106 }
107
108 #[must_use]
113 pub const fn is_empty(&self) -> bool {
114 self.0.is_empty()
115 }
116
117 #[must_use]
119 pub fn iter(&self) -> impl ExactSizeIterator<Item = &PendingNodeResultHead> {
120 self.0.iter()
121 }
122
123 #[must_use]
125 pub const fn as_slice(&self) -> &[PendingNodeResultHead] {
126 &self.0
127 }
128}
129
130impl Serialize for BarrierResultHeads {
131 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
132 where
133 S: serde::Serializer,
134 {
135 self.0.serialize(serializer)
136 }
137}
138
139impl<'de> Deserialize<'de> for BarrierResultHeads {
140 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
141 where
142 D: Deserializer<'de>,
143 {
144 deserializer.deserialize_seq(BarrierResultHeadsVisitor)
145 }
146}
147
148struct BarrierResultHeadsVisitor;
149
150impl<'de> de::Visitor<'de> for BarrierResultHeadsVisitor {
151 type Value = BarrierResultHeads;
152
153 fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
154 write!(
155 formatter,
156 "one to {} unique root-graph pending result heads",
157 BarrierResultHeads::MAX_LEN
158 )
159 }
160
161 fn visit_seq<A>(self, mut sequence: A) -> Result<Self::Value, A::Error>
162 where
163 A: SeqAccess<'de>,
164 {
165 let mut values = Vec::with_capacity(
166 sequence
167 .size_hint()
168 .unwrap_or_default()
169 .min(BarrierResultHeads::MAX_LEN),
170 );
171 while let Some(value) = sequence.next_element::<PendingNodeResultHead>()? {
172 if values.len() == BarrierResultHeads::MAX_LEN {
173 return Err(de::Error::custom(BarrierResultHeadsError::TooMany {
174 maximum: BarrierResultHeads::MAX_LEN,
175 actual: BarrierResultHeads::MAX_LEN + 1,
176 }));
177 }
178 values.push(value);
179 }
180 BarrierResultHeads::try_new(values).map_err(de::Error::custom)
181 }
182}
183
184impl JsonSchema for BarrierResultHeads {
185 fn schema_name() -> std::borrow::Cow<'static, str> {
186 "BarrierResultHeads".into()
187 }
188
189 fn schema_id() -> std::borrow::Cow<'static, str> {
190 concat!(module_path!(), "::BarrierResultHeads").into()
191 }
192
193 fn json_schema(generator: &mut SchemaGenerator) -> Schema {
194 json_schema!({
195 "type": "array",
196 "items": generator.subschema_for::<PendingNodeResultHead>(),
197 "minItems": 1,
198 "maxItems": 1024,
199 "uniqueItems": true,
200 "description": "Serialized in canonical (graph_namespace, node_id) order; runtime additionally requires one exact base checkpoint."
201 })
202 }
203}
204
205#[derive(Clone, Debug, Eq, Error, PartialEq)]
207#[non_exhaustive]
208pub enum BarrierResultHeadsError {
209 #[error("checkpoint barrier result set must not be empty")]
211 Empty,
212 #[error("checkpoint barrier contains {actual} results; maximum is {maximum}")]
214 TooMany {
215 maximum: usize,
217 actual: usize,
219 },
220 #[error("checkpoint barrier contains a duplicate logical activation")]
222 DuplicateActivation {
223 namespace: GraphNamespace,
225 node_id: NodeId,
227 },
228 #[error("checkpoint barrier result heads use different base checkpoints")]
230 MixedBaseCheckpoints,
231 #[error("checkpoint barrier result belongs to an unsupported nested graph namespace")]
233 NestedGraphNamespace {
234 namespace: GraphNamespace,
236 },
237}
238
239#[derive(Clone, Eq, JsonSchema, PartialEq, Serialize)]
245#[serde(deny_unknown_fields)]
246pub struct CheckpointBarrier {
247 base_checkpoint: CheckpointHead,
248 base_ready_nodes: ReadyNodes,
249 result_heads: BarrierResultHeads,
250 successor: CheckpointWrite,
251 intent_digest: Digest,
252}
253
254impl CheckpointBarrier {
255 pub fn new<I>(
263 base: &Checkpoint,
264 successor: CheckpointWrite,
265 result_heads: I,
266 ) -> Result<Self, CheckpointBarrierError>
267 where
268 I: IntoIterator<Item = PendingNodeResultHead>,
269 {
270 let result_heads =
271 BarrierResultHeads::try_new(result_heads).map_err(CheckpointBarrierError::results)?;
272 Self::build(
273 base.head(),
274 base.ready_nodes().clone(),
275 result_heads,
276 successor,
277 None,
278 )
279 }
280
281 pub fn restore(
291 base_checkpoint: CheckpointHead,
292 base_ready_nodes: ReadyNodes,
293 result_heads: BarrierResultHeads,
294 successor: CheckpointWrite,
295 intent_digest: Digest,
296 ) -> Result<Self, CheckpointBarrierError> {
297 Self::build(
298 base_checkpoint,
299 base_ready_nodes,
300 result_heads,
301 successor,
302 Some(intent_digest),
303 )
304 }
305
306 fn build(
307 base_checkpoint: CheckpointHead,
308 base_ready_nodes: ReadyNodes,
309 result_heads: BarrierResultHeads,
310 successor: CheckpointWrite,
311 supplied_digest: Option<Digest>,
312 ) -> Result<Self, CheckpointBarrierError> {
313 validate_barrier_shape(
314 &base_checkpoint,
315 &base_ready_nodes,
316 &result_heads,
317 &successor,
318 )?;
319 let intent_digest = compute_barrier_digest(&CheckpointBarrierDigestWire {
320 base_checkpoint: &base_checkpoint,
321 base_ready_nodes: &base_ready_nodes,
322 result_heads: &result_heads,
323 successor_intent_digest: successor.intent_digest(),
324 })?;
325 if supplied_digest.is_some_and(|supplied| supplied != intent_digest) {
326 return Err(CheckpointBarrierError::DigestMismatch);
327 }
328 Ok(Self {
329 base_checkpoint,
330 base_ready_nodes,
331 result_heads,
332 successor,
333 intent_digest,
334 })
335 }
336
337 #[must_use]
339 pub const fn base_checkpoint(&self) -> &CheckpointHead {
340 &self.base_checkpoint
341 }
342
343 #[must_use]
345 pub const fn base_ready_nodes(&self) -> &ReadyNodes {
346 &self.base_ready_nodes
347 }
348
349 #[must_use]
351 pub const fn result_heads(&self) -> &BarrierResultHeads {
352 &self.result_heads
353 }
354
355 #[must_use]
357 pub const fn successor(&self) -> &CheckpointWrite {
358 &self.successor
359 }
360
361 #[must_use]
363 pub fn into_successor(self) -> CheckpointWrite {
364 self.successor
365 }
366
367 #[must_use]
369 pub const fn intent_digest(&self) -> Digest {
370 self.intent_digest
371 }
372}
373
374impl fmt::Debug for CheckpointBarrier {
375 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
376 formatter
377 .debug_struct("CheckpointBarrier")
378 .field("base_checkpoint", &self.base_checkpoint)
379 .field("base_ready_count", &self.base_ready_nodes.len())
380 .field("result_count", &self.result_heads.len())
381 .field("successor", &self.successor)
382 .field("intent_digest", &self.intent_digest)
383 .finish_non_exhaustive()
384 }
385}
386
387impl<'de> Deserialize<'de> for CheckpointBarrier {
388 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
389 where
390 D: Deserializer<'de>,
391 {
392 #[derive(Deserialize)]
393 #[serde(deny_unknown_fields)]
394 struct Wire {
395 base_checkpoint: CheckpointHead,
396 base_ready_nodes: ReadyNodes,
397 result_heads: BarrierResultHeads,
398 successor: CheckpointWrite,
399 intent_digest: Digest,
400 }
401
402 let wire = Wire::deserialize(deserializer)?;
403 Self::restore(
404 wire.base_checkpoint,
405 wire.base_ready_nodes,
406 wire.result_heads,
407 wire.successor,
408 wire.intent_digest,
409 )
410 .map_err(de::Error::custom)
411 }
412}
413
414#[derive(Clone, Debug, Eq, Error, PartialEq)]
416#[non_exhaustive]
417pub enum CheckpointBarrierError {
418 #[error("checkpoint barrier result set is invalid: {source}")]
420 Results {
421 #[source]
423 source: BarrierResultHeadsError,
424 },
425 #[error("checkpoint barrier base ready set must not be empty")]
427 EmptyReadySet,
428 #[error("checkpoint barrier successor does not name the exact base checkpoint")]
430 SuccessorParentMismatch,
431 #[error("checkpoint barrier result does not belong to the base checkpoint")]
433 ResultBaseMismatch,
434 #[error("checkpoint barrier result node was not ready in the base checkpoint")]
436 UnexpectedResultNode {
437 node_id: NodeId,
439 },
440 #[error("checkpoint barrier does not contain every base ready node")]
442 MissingResultNode {
443 node_id: NodeId,
445 },
446 #[error("checkpoint barrier intent integrity calculation failed: {source}")]
448 Integrity {
449 #[source]
451 source: CheckpointBarrierIntegrityError,
452 },
453 #[error("checkpoint barrier intent digest does not match its fields")]
455 DigestMismatch,
456}
457
458impl CheckpointBarrierError {
459 const fn results(source: BarrierResultHeadsError) -> Self {
460 Self::Results { source }
461 }
462}
463
464impl From<CheckpointBarrierIntegrityError> for CheckpointBarrierError {
465 fn from(source: CheckpointBarrierIntegrityError) -> Self {
466 Self::Integrity { source }
467 }
468}
469
470fn validate_barrier_shape(
471 base_checkpoint: &CheckpointHead,
472 base_ready_nodes: &ReadyNodes,
473 result_heads: &BarrierResultHeads,
474 successor: &CheckpointWrite,
475) -> Result<(), CheckpointBarrierError> {
476 if base_ready_nodes.is_empty() {
477 return Err(CheckpointBarrierError::EmptyReadySet);
478 }
479 if successor.parent() != Some(base_checkpoint) {
480 return Err(CheckpointBarrierError::SuccessorParentMismatch);
481 }
482 let mut observed = BTreeSet::new();
483 for head in result_heads.iter() {
484 let activation = head.activation();
485 if activation.base_checkpoint() != base_checkpoint {
486 return Err(CheckpointBarrierError::ResultBaseMismatch);
487 }
488 if !base_ready_nodes.contains(activation.node_id()) {
489 return Err(CheckpointBarrierError::UnexpectedResultNode {
490 node_id: activation.node_id().clone(),
491 });
492 }
493 observed.insert(activation.node_id().clone());
494 }
495 for node_id in base_ready_nodes {
496 if !observed.contains(node_id) {
497 return Err(CheckpointBarrierError::MissingResultNode {
498 node_id: node_id.clone(),
499 });
500 }
501 }
502 Ok(())
503}
504
505#[derive(Serialize)]
506struct CheckpointBarrierDigestWire<'a> {
507 base_checkpoint: &'a CheckpointHead,
508 base_ready_nodes: &'a ReadyNodes,
509 result_heads: &'a BarrierResultHeads,
510 successor_intent_digest: Digest,
511}
512
513fn compute_barrier_digest(
514 value: &CheckpointBarrierDigestWire<'_>,
515) -> Result<Digest, CheckpointBarrierIntegrityError> {
516 let canonical = serde_json_canonicalizer::to_vec(value)
517 .map_err(|_| CheckpointBarrierIntegrityError::CanonicalSerialization)?;
518 let mut preimage = Vec::with_capacity(BARRIER_INTENT_DIGEST_DOMAIN.len() + canonical.len());
519 preimage.extend_from_slice(BARRIER_INTENT_DIGEST_DOMAIN);
520 preimage.extend_from_slice(&canonical);
521 Ok(Digest::sha256(preimage))
522}
523
524#[derive(Clone, Debug, Eq, Error, PartialEq)]
526#[non_exhaustive]
527pub enum CheckpointBarrierIntegrityError {
528 #[error("checkpoint barrier checksum preimage serialization failed")]
530 CanonicalSerialization,
531}
532
533#[cfg(test)]
534mod tests {
535 use super::*;
536 use crate::{
537 AttemptId, CheckpointId, FencingEpoch, GraphNamespace, JournalHead, JournalSequence,
538 NodeActivation, PendingNodeResult, PendingNodeResultIntent, RunFence, Timestamp,
539 };
540 use serde_json::{Value, from_value, json, to_value};
541
542 fn checkpoint() -> Checkpoint {
543 let fixture: Value =
544 serde_json::from_str(include_str!("../tests/fixtures/core-checkpoint-v1.json"))
545 .unwrap();
546 from_value(fixture["checkpoints"][0].clone()).unwrap()
547 }
548
549 fn result(base: &Checkpoint, node_id: NodeId, sequence: u64) -> PendingNodeResult {
550 let activation = NodeActivation::new(
551 base.head(),
552 GraphNamespace::root(),
553 node_id,
554 Digest::sha256(sequence.to_be_bytes()),
555 );
556 let intent = PendingNodeResultIntent::new(
557 activation.clone(),
558 crate::NodeStateChange::Unchanged,
559 crate::NodeControl::Continue,
560 crate::NodeInvocationBindings::empty(),
561 )
562 .unwrap();
563 let recorded_at = Timestamp::from_unix_micros(
564 base.journal_head().recorded_at().unix_micros()
565 + i64::try_from(sequence).unwrap() * 1_000_000,
566 )
567 .unwrap();
568 let event_id = format!("01912345-6789-7abc-8def-0123456789{sequence:02x}")
569 .parse()
570 .unwrap();
571 let journal = JournalHead::new(
572 base.tenant_id().clone(),
573 base.run_id(),
574 JournalSequence::new(base.journal_head().sequence().get() + sequence).unwrap(),
575 event_id,
576 recorded_at,
577 Digest::sha256(format!("result-{sequence}")),
578 );
579 let fence = RunFence::new(
580 base.tenant_id().clone(),
581 base.run_id(),
582 format!("01912345-6789-7abc-8def-0123456788{sequence:02x}")
583 .parse::<AttemptId>()
584 .unwrap(),
585 FencingEpoch::new(sequence).unwrap(),
586 );
587 PendingNodeResult::commit(intent, fence, journal).unwrap()
588 }
589
590 fn successor(base: &Checkpoint) -> CheckpointWrite {
591 CheckpointWrite::successor(
592 CheckpointId::generate(),
593 base,
594 base.state().clone(),
595 ReadyNodes::empty(),
596 )
597 .unwrap()
598 }
599
600 #[test]
601 fn exact_ready_coverage_is_canonical_and_integrity_bound() {
602 let base = checkpoint();
603 let heads = base
604 .ready_nodes()
605 .iter()
606 .rev()
607 .enumerate()
608 .map(|(index, node_id)| {
609 result(&base, node_id.clone(), u64::try_from(index + 1).unwrap()).head()
610 })
611 .collect::<Vec<_>>();
612 let barrier = CheckpointBarrier::new(&base, successor(&base), heads).unwrap();
613 assert_eq!(barrier.result_heads().len(), base.ready_nodes().len());
614 assert!(
615 barrier
616 .result_heads()
617 .iter()
618 .map(|head| head.activation().node_id())
619 .is_sorted()
620 );
621 assert_eq!(
622 from_value::<CheckpointBarrier>(to_value(&barrier).unwrap()).unwrap(),
623 barrier
624 );
625
626 let mut changed = to_value(&barrier).unwrap();
627 changed["successor"]["ready_nodes"] = json!(["substituted"]);
628 assert!(from_value::<CheckpointBarrier>(changed).is_err());
629 }
630
631 #[test]
632 fn barrier_rejects_missing_unexpected_mixed_and_nested_results() {
633 let base = checkpoint();
634 let first = base.ready_nodes().iter().next().unwrap().clone();
635 let one = result(&base, first.clone(), 1).head();
636 if base.ready_nodes().len() > 1 {
637 assert!(matches!(
638 CheckpointBarrier::new(&base, successor(&base), [one.clone()]),
639 Err(CheckpointBarrierError::MissingResultNode { .. })
640 ));
641 }
642
643 let unexpected = result(&base, NodeId::new("unexpected").unwrap(), 2).head();
644 assert!(matches!(
645 CheckpointBarrier::new(&base, successor(&base), [unexpected]),
646 Err(CheckpointBarrierError::UnexpectedResultNode { .. })
647 ));
648
649 let other_base = Checkpoint::commit(successor(&base), one.journal_head().clone()).unwrap();
650 let mixed = result(&other_base, NodeId::new("nested-result").unwrap(), 3).head();
651 assert!(matches!(
652 BarrierResultHeads::try_new([one.clone(), mixed]),
653 Err(BarrierResultHeadsError::MixedBaseCheckpoints)
654 ));
655
656 let nested_activation = NodeActivation::new(
657 base.head(),
658 GraphNamespace::new("nested").unwrap(),
659 first,
660 Digest::sha256(b"nested"),
661 );
662 let nested_intent = PendingNodeResultIntent::new(
663 nested_activation.clone(),
664 crate::NodeStateChange::Unchanged,
665 crate::NodeControl::Continue,
666 crate::NodeInvocationBindings::empty(),
667 )
668 .unwrap();
669 let nested = PendingNodeResult::commit(
670 nested_intent,
671 RunFence::new(
672 base.tenant_id().clone(),
673 base.run_id(),
674 "01912345-6789-7abc-8def-0123456788ff".parse().unwrap(),
675 FencingEpoch::FIRST,
676 ),
677 one.journal_head().clone(),
678 )
679 .unwrap();
680 assert!(matches!(
681 BarrierResultHeads::try_new([nested.head()]),
682 Err(BarrierResultHeadsError::NestedGraphNamespace { .. })
683 ));
684 }
685}