use std::{collections::BTreeSet, fmt};
use schemars::{JsonSchema, Schema, SchemaGenerator, json_schema};
use serde::{
Deserialize, Deserializer, Serialize,
de::{self, SeqAccess},
};
use thiserror::Error;
use crate::{
Checkpoint, CheckpointHead, CheckpointWrite, Digest, GraphNamespace, NodeId,
PendingNodeResultHead, ReadyNodes,
};
const BARRIER_INTENT_DIGEST_DOMAIN: &[u8] = b"stateknot-checkpoint-barrier-intent-v1\0";
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct BarrierResultHeads(Box<[PendingNodeResultHead]>);
impl BarrierResultHeads {
pub const MAX_LEN: usize = ReadyNodes::MAX_LEN;
pub fn try_new<I>(values: I) -> Result<Self, BarrierResultHeadsError>
where
I: IntoIterator<Item = PendingNodeResultHead>,
{
let mut collected = Vec::new();
let mut identities = BTreeSet::new();
let mut base: Option<CheckpointHead> = None;
for value in values {
if collected.len() == Self::MAX_LEN {
return Err(BarrierResultHeadsError::TooMany {
maximum: Self::MAX_LEN,
actual: Self::MAX_LEN + 1,
});
}
let activation = value.activation();
if !activation.graph_namespace().is_root() {
return Err(BarrierResultHeadsError::NestedGraphNamespace {
namespace: activation.graph_namespace().clone(),
});
}
if let Some(expected) = &base {
if activation.base_checkpoint() != expected {
return Err(BarrierResultHeadsError::MixedBaseCheckpoints);
}
} else {
base = Some(activation.base_checkpoint().clone());
}
let identity = (
activation.graph_namespace().clone(),
activation.node_id().clone(),
);
if !identities.insert(identity.clone()) {
return Err(BarrierResultHeadsError::DuplicateActivation {
namespace: identity.0,
node_id: identity.1,
});
}
collected.push(value);
}
if collected.is_empty() {
return Err(BarrierResultHeadsError::Empty);
}
collected.sort_unstable_by(|left, right| {
let left = left.activation();
let right = right.activation();
(left.graph_namespace(), left.node_id())
.cmp(&(right.graph_namespace(), right.node_id()))
});
Ok(Self(collected.into_boxed_slice()))
}
#[must_use]
pub const fn len(&self) -> usize {
self.0.len()
}
#[must_use]
pub const fn is_empty(&self) -> bool {
self.0.is_empty()
}
#[must_use]
pub fn iter(&self) -> impl ExactSizeIterator<Item = &PendingNodeResultHead> {
self.0.iter()
}
#[must_use]
pub const fn as_slice(&self) -> &[PendingNodeResultHead] {
&self.0
}
}
impl Serialize for BarrierResultHeads {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
self.0.serialize(serializer)
}
}
impl<'de> Deserialize<'de> for BarrierResultHeads {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
deserializer.deserialize_seq(BarrierResultHeadsVisitor)
}
}
struct BarrierResultHeadsVisitor;
impl<'de> de::Visitor<'de> for BarrierResultHeadsVisitor {
type Value = BarrierResultHeads;
fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
formatter,
"one to {} unique root-graph pending result heads",
BarrierResultHeads::MAX_LEN
)
}
fn visit_seq<A>(self, mut sequence: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
let mut values = Vec::with_capacity(
sequence
.size_hint()
.unwrap_or_default()
.min(BarrierResultHeads::MAX_LEN),
);
while let Some(value) = sequence.next_element::<PendingNodeResultHead>()? {
if values.len() == BarrierResultHeads::MAX_LEN {
return Err(de::Error::custom(BarrierResultHeadsError::TooMany {
maximum: BarrierResultHeads::MAX_LEN,
actual: BarrierResultHeads::MAX_LEN + 1,
}));
}
values.push(value);
}
BarrierResultHeads::try_new(values).map_err(de::Error::custom)
}
}
impl JsonSchema for BarrierResultHeads {
fn schema_name() -> std::borrow::Cow<'static, str> {
"BarrierResultHeads".into()
}
fn schema_id() -> std::borrow::Cow<'static, str> {
concat!(module_path!(), "::BarrierResultHeads").into()
}
fn json_schema(generator: &mut SchemaGenerator) -> Schema {
json_schema!({
"type": "array",
"items": generator.subschema_for::<PendingNodeResultHead>(),
"minItems": 1,
"maxItems": 1024,
"uniqueItems": true,
"description": "Serialized in canonical (graph_namespace, node_id) order; runtime additionally requires one exact base checkpoint."
})
}
}
#[derive(Clone, Debug, Eq, Error, PartialEq)]
#[non_exhaustive]
pub enum BarrierResultHeadsError {
#[error("checkpoint barrier result set must not be empty")]
Empty,
#[error("checkpoint barrier contains {actual} results; maximum is {maximum}")]
TooMany {
maximum: usize,
actual: usize,
},
#[error("checkpoint barrier contains a duplicate logical activation")]
DuplicateActivation {
namespace: GraphNamespace,
node_id: NodeId,
},
#[error("checkpoint barrier result heads use different base checkpoints")]
MixedBaseCheckpoints,
#[error("checkpoint barrier result belongs to an unsupported nested graph namespace")]
NestedGraphNamespace {
namespace: GraphNamespace,
},
}
#[derive(Clone, Eq, JsonSchema, PartialEq, Serialize)]
#[serde(deny_unknown_fields)]
pub struct CheckpointBarrier {
base_checkpoint: CheckpointHead,
base_ready_nodes: ReadyNodes,
result_heads: BarrierResultHeads,
successor: CheckpointWrite,
intent_digest: Digest,
}
impl CheckpointBarrier {
pub fn new<I>(
base: &Checkpoint,
successor: CheckpointWrite,
result_heads: I,
) -> Result<Self, CheckpointBarrierError>
where
I: IntoIterator<Item = PendingNodeResultHead>,
{
let result_heads =
BarrierResultHeads::try_new(result_heads).map_err(CheckpointBarrierError::results)?;
Self::build(
base.head(),
base.ready_nodes().clone(),
result_heads,
successor,
None,
)
}
pub fn restore(
base_checkpoint: CheckpointHead,
base_ready_nodes: ReadyNodes,
result_heads: BarrierResultHeads,
successor: CheckpointWrite,
intent_digest: Digest,
) -> Result<Self, CheckpointBarrierError> {
Self::build(
base_checkpoint,
base_ready_nodes,
result_heads,
successor,
Some(intent_digest),
)
}
fn build(
base_checkpoint: CheckpointHead,
base_ready_nodes: ReadyNodes,
result_heads: BarrierResultHeads,
successor: CheckpointWrite,
supplied_digest: Option<Digest>,
) -> Result<Self, CheckpointBarrierError> {
validate_barrier_shape(
&base_checkpoint,
&base_ready_nodes,
&result_heads,
&successor,
)?;
let intent_digest = compute_barrier_digest(&CheckpointBarrierDigestWire {
base_checkpoint: &base_checkpoint,
base_ready_nodes: &base_ready_nodes,
result_heads: &result_heads,
successor_intent_digest: successor.intent_digest(),
})?;
if supplied_digest.is_some_and(|supplied| supplied != intent_digest) {
return Err(CheckpointBarrierError::DigestMismatch);
}
Ok(Self {
base_checkpoint,
base_ready_nodes,
result_heads,
successor,
intent_digest,
})
}
#[must_use]
pub const fn base_checkpoint(&self) -> &CheckpointHead {
&self.base_checkpoint
}
#[must_use]
pub const fn base_ready_nodes(&self) -> &ReadyNodes {
&self.base_ready_nodes
}
#[must_use]
pub const fn result_heads(&self) -> &BarrierResultHeads {
&self.result_heads
}
#[must_use]
pub const fn successor(&self) -> &CheckpointWrite {
&self.successor
}
#[must_use]
pub fn into_successor(self) -> CheckpointWrite {
self.successor
}
#[must_use]
pub const fn intent_digest(&self) -> Digest {
self.intent_digest
}
}
impl fmt::Debug for CheckpointBarrier {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter
.debug_struct("CheckpointBarrier")
.field("base_checkpoint", &self.base_checkpoint)
.field("base_ready_count", &self.base_ready_nodes.len())
.field("result_count", &self.result_heads.len())
.field("successor", &self.successor)
.field("intent_digest", &self.intent_digest)
.finish_non_exhaustive()
}
}
impl<'de> Deserialize<'de> for CheckpointBarrier {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
#[derive(Deserialize)]
#[serde(deny_unknown_fields)]
struct Wire {
base_checkpoint: CheckpointHead,
base_ready_nodes: ReadyNodes,
result_heads: BarrierResultHeads,
successor: CheckpointWrite,
intent_digest: Digest,
}
let wire = Wire::deserialize(deserializer)?;
Self::restore(
wire.base_checkpoint,
wire.base_ready_nodes,
wire.result_heads,
wire.successor,
wire.intent_digest,
)
.map_err(de::Error::custom)
}
}
#[derive(Clone, Debug, Eq, Error, PartialEq)]
#[non_exhaustive]
pub enum CheckpointBarrierError {
#[error("checkpoint barrier result set is invalid: {source}")]
Results {
#[source]
source: BarrierResultHeadsError,
},
#[error("checkpoint barrier base ready set must not be empty")]
EmptyReadySet,
#[error("checkpoint barrier successor does not name the exact base checkpoint")]
SuccessorParentMismatch,
#[error("checkpoint barrier result does not belong to the base checkpoint")]
ResultBaseMismatch,
#[error("checkpoint barrier result node was not ready in the base checkpoint")]
UnexpectedResultNode {
node_id: NodeId,
},
#[error("checkpoint barrier does not contain every base ready node")]
MissingResultNode {
node_id: NodeId,
},
#[error("checkpoint barrier intent integrity calculation failed: {source}")]
Integrity {
#[source]
source: CheckpointBarrierIntegrityError,
},
#[error("checkpoint barrier intent digest does not match its fields")]
DigestMismatch,
}
impl CheckpointBarrierError {
const fn results(source: BarrierResultHeadsError) -> Self {
Self::Results { source }
}
}
impl From<CheckpointBarrierIntegrityError> for CheckpointBarrierError {
fn from(source: CheckpointBarrierIntegrityError) -> Self {
Self::Integrity { source }
}
}
fn validate_barrier_shape(
base_checkpoint: &CheckpointHead,
base_ready_nodes: &ReadyNodes,
result_heads: &BarrierResultHeads,
successor: &CheckpointWrite,
) -> Result<(), CheckpointBarrierError> {
if base_ready_nodes.is_empty() {
return Err(CheckpointBarrierError::EmptyReadySet);
}
if successor.parent() != Some(base_checkpoint) {
return Err(CheckpointBarrierError::SuccessorParentMismatch);
}
let mut observed = BTreeSet::new();
for head in result_heads.iter() {
let activation = head.activation();
if activation.base_checkpoint() != base_checkpoint {
return Err(CheckpointBarrierError::ResultBaseMismatch);
}
if !base_ready_nodes.contains(activation.node_id()) {
return Err(CheckpointBarrierError::UnexpectedResultNode {
node_id: activation.node_id().clone(),
});
}
observed.insert(activation.node_id().clone());
}
for node_id in base_ready_nodes {
if !observed.contains(node_id) {
return Err(CheckpointBarrierError::MissingResultNode {
node_id: node_id.clone(),
});
}
}
Ok(())
}
#[derive(Serialize)]
struct CheckpointBarrierDigestWire<'a> {
base_checkpoint: &'a CheckpointHead,
base_ready_nodes: &'a ReadyNodes,
result_heads: &'a BarrierResultHeads,
successor_intent_digest: Digest,
}
fn compute_barrier_digest(
value: &CheckpointBarrierDigestWire<'_>,
) -> Result<Digest, CheckpointBarrierIntegrityError> {
let canonical = serde_json_canonicalizer::to_vec(value)
.map_err(|_| CheckpointBarrierIntegrityError::CanonicalSerialization)?;
let mut preimage = Vec::with_capacity(BARRIER_INTENT_DIGEST_DOMAIN.len() + canonical.len());
preimage.extend_from_slice(BARRIER_INTENT_DIGEST_DOMAIN);
preimage.extend_from_slice(&canonical);
Ok(Digest::sha256(preimage))
}
#[derive(Clone, Debug, Eq, Error, PartialEq)]
#[non_exhaustive]
pub enum CheckpointBarrierIntegrityError {
#[error("checkpoint barrier checksum preimage serialization failed")]
CanonicalSerialization,
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
AttemptId, CheckpointId, FencingEpoch, GraphNamespace, JournalHead, JournalSequence,
NodeActivation, PendingNodeResult, PendingNodeResultIntent, RunFence, Timestamp,
};
use serde_json::{Value, from_value, json, to_value};
fn checkpoint() -> Checkpoint {
let fixture: Value =
serde_json::from_str(include_str!("../tests/fixtures/core-checkpoint-v1.json"))
.unwrap();
from_value(fixture["checkpoints"][0].clone()).unwrap()
}
fn result(base: &Checkpoint, node_id: NodeId, sequence: u64) -> PendingNodeResult {
let activation = NodeActivation::new(
base.head(),
GraphNamespace::root(),
node_id,
Digest::sha256(sequence.to_be_bytes()),
);
let intent = PendingNodeResultIntent::new(
activation.clone(),
crate::NodeStateChange::Unchanged,
crate::NodeControl::Continue,
crate::NodeInvocationBindings::empty(),
)
.unwrap();
let recorded_at = Timestamp::from_unix_micros(
base.journal_head().recorded_at().unix_micros()
+ i64::try_from(sequence).unwrap() * 1_000_000,
)
.unwrap();
let event_id = format!("01912345-6789-7abc-8def-0123456789{sequence:02x}")
.parse()
.unwrap();
let journal = JournalHead::new(
base.tenant_id().clone(),
base.run_id(),
JournalSequence::new(base.journal_head().sequence().get() + sequence).unwrap(),
event_id,
recorded_at,
Digest::sha256(format!("result-{sequence}")),
);
let fence = RunFence::new(
base.tenant_id().clone(),
base.run_id(),
format!("01912345-6789-7abc-8def-0123456788{sequence:02x}")
.parse::<AttemptId>()
.unwrap(),
FencingEpoch::new(sequence).unwrap(),
);
PendingNodeResult::commit(intent, fence, journal).unwrap()
}
fn successor(base: &Checkpoint) -> CheckpointWrite {
CheckpointWrite::successor(
CheckpointId::generate(),
base,
base.state().clone(),
ReadyNodes::empty(),
)
.unwrap()
}
#[test]
fn exact_ready_coverage_is_canonical_and_integrity_bound() {
let base = checkpoint();
let heads = base
.ready_nodes()
.iter()
.rev()
.enumerate()
.map(|(index, node_id)| {
result(&base, node_id.clone(), u64::try_from(index + 1).unwrap()).head()
})
.collect::<Vec<_>>();
let barrier = CheckpointBarrier::new(&base, successor(&base), heads).unwrap();
assert_eq!(barrier.result_heads().len(), base.ready_nodes().len());
assert!(
barrier
.result_heads()
.iter()
.map(|head| head.activation().node_id())
.is_sorted()
);
assert_eq!(
from_value::<CheckpointBarrier>(to_value(&barrier).unwrap()).unwrap(),
barrier
);
let mut changed = to_value(&barrier).unwrap();
changed["successor"]["ready_nodes"] = json!(["substituted"]);
assert!(from_value::<CheckpointBarrier>(changed).is_err());
}
#[test]
fn barrier_rejects_missing_unexpected_mixed_and_nested_results() {
let base = checkpoint();
let first = base.ready_nodes().iter().next().unwrap().clone();
let one = result(&base, first.clone(), 1).head();
if base.ready_nodes().len() > 1 {
assert!(matches!(
CheckpointBarrier::new(&base, successor(&base), [one.clone()]),
Err(CheckpointBarrierError::MissingResultNode { .. })
));
}
let unexpected = result(&base, NodeId::new("unexpected").unwrap(), 2).head();
assert!(matches!(
CheckpointBarrier::new(&base, successor(&base), [unexpected]),
Err(CheckpointBarrierError::UnexpectedResultNode { .. })
));
let other_base = Checkpoint::commit(successor(&base), one.journal_head().clone()).unwrap();
let mixed = result(&other_base, NodeId::new("nested-result").unwrap(), 3).head();
assert!(matches!(
BarrierResultHeads::try_new([one.clone(), mixed]),
Err(BarrierResultHeadsError::MixedBaseCheckpoints)
));
let nested_activation = NodeActivation::new(
base.head(),
GraphNamespace::new("nested").unwrap(),
first,
Digest::sha256(b"nested"),
);
let nested_intent = PendingNodeResultIntent::new(
nested_activation.clone(),
crate::NodeStateChange::Unchanged,
crate::NodeControl::Continue,
crate::NodeInvocationBindings::empty(),
)
.unwrap();
let nested = PendingNodeResult::commit(
nested_intent,
RunFence::new(
base.tenant_id().clone(),
base.run_id(),
"01912345-6789-7abc-8def-0123456788ff".parse().unwrap(),
FencingEpoch::FIRST,
),
one.journal_head().clone(),
)
.unwrap();
assert!(matches!(
BarrierResultHeads::try_new([nested.head()]),
Err(BarrierResultHeadsError::NestedGraphNamespace { .. })
));
}
}