use crate::record::{Header, LinkType};
use crate::store::{CheckpointedLog, RecordSource};
use crate::substrate::SubstrateError;
use serde::{Deserialize, Serialize};
use std::collections::BTreeMap;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "SCREAMING_SNAKE_CASE")]
pub enum PairState {
Matched,
AOnly,
BOnly,
Conflicting,
Insufficient,
Unresolved,
}
impl PairState {
pub const ALL: [PairState; 6] = [
PairState::Matched,
PairState::AOnly,
PairState::BOnly,
PairState::Conflicting,
PairState::Insufficient,
PairState::Unresolved,
];
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct JoinPolicy {
pub primary: String,
pub secondary: String,
pub group: Option<String>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Half {
pub record_id: String,
pub seq: u64,
pub correlation: BTreeMap<String, String>,
pub payload_commitments: Vec<String>,
pub covered: bool,
pub trusted: bool,
pub failed: bool,
}
impl Half {
fn key(&self, name: &str) -> Option<&str> {
self.correlation
.get(name)
.map(String::as_str)
.filter(|v| !v.is_empty())
}
fn has_no_keys(&self) -> bool {
self.correlation.values().all(String::is_empty)
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct HalfSet {
pub halves: Vec<Half>,
pub complete: bool,
}
impl HalfSet {
pub fn from_store(
log: &dyn CheckpointedLog,
records: &dyn RecordSource,
ids: &[String],
complete: bool,
) -> Result<Self, SubstrateError> {
let covered = match log.stated_checkpoints()?.last() {
Some(cp) => cp.checkpoint.leaf_count()?,
None => 0,
};
let halves = ids
.iter()
.filter_map(|id| records.record_by_digest(id).filter(|r| r.digest == *id))
.map(|r| {
let header = (records.entry_of(&r.body).as_deref() == Some(r.digest.as_str()))
.then(|| serde_json::from_slice::<Header>(&r.body).ok())
.flatten()
.filter(|h| h.validate().is_ok());
let (seq, correlation, payload_commitments, trusted) = match header {
Some(h) => (h.seq, h.correlation, h.payload_commitments, true),
None => (0, BTreeMap::new(), Vec::new(), false),
};
Half {
record_id: r.digest,
seq,
correlation,
payload_commitments,
covered: r.leaf_index < covered,
trusted,
failed: false,
}
})
.collect();
Ok(Self { halves, complete })
}
}
pub type Comparator<'a> = &'a dyn Fn(&Half, &Half) -> bool;
pub fn same_payload_commitments(a: &Half, b: &Half) -> bool {
!a.payload_commitments.is_empty() && a.payload_commitments == b.payload_commitments
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct PairResult {
pub state: PairState,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub join_key: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub a: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub b: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub group: Option<String>,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct Tallies {
#[serde(rename = "MATCHED")]
pub matched: usize,
#[serde(rename = "A_ONLY")]
pub a_only: usize,
#[serde(rename = "B_ONLY")]
pub b_only: usize,
#[serde(rename = "CONFLICTING")]
pub conflicting: usize,
#[serde(rename = "INSUFFICIENT")]
pub insufficient: usize,
#[serde(rename = "UNRESOLVED")]
pub unresolved: usize,
}
impl Tallies {
fn add(&mut self, state: PairState) {
match state {
PairState::Matched => self.matched += 1,
PairState::AOnly => self.a_only += 1,
PairState::BOnly => self.b_only += 1,
PairState::Conflicting => self.conflicting += 1,
PairState::Insufficient => self.insufficient += 1,
PairState::Unresolved => self.unresolved += 1,
}
}
}
pub fn reconcile_halves(
a: &HalfSet,
b: &HalfSet,
policy: &JoinPolicy,
compare: Comparator<'_>,
) -> (Vec<PairResult>, Tallies) {
let mut partner: Vec<Option<usize>> = vec![None; a.halves.len()];
let mut joined_on: Vec<Option<&str>> = vec![None; a.halves.len()];
let mut used = vec![false; b.halves.len()];
let pick = |used: &[bool], matches: &dyn Fn(&Half) -> bool| {
b.halves
.iter()
.enumerate()
.find(|(j, h)| !used[*j] && matches(h))
.map(|(j, _)| j)
};
let compatible = |x: &Half, y: &Half| match (x.key(&policy.secondary), y.key(&policy.secondary))
{
(Some(p), Some(q)) => p == q,
_ => true,
};
type Tier<'t> = &'t dyn Fn(&Half, &Half) -> bool;
let tiers: [Tier<'_>; 5] = [
&|own, h| {
h.failed == own.failed
&& own.key(&policy.secondary).is_some()
&& own.key(&policy.secondary) == h.key(&policy.secondary)
},
&|own, h| h.failed == own.failed && compatible(own, h),
&|own, h| h.failed == own.failed,
&|own, h| compatible(own, h),
&|_, _| true,
];
for tier in tiers {
for (i, own) in a.halves.iter().enumerate() {
if partner[i].is_some() {
continue;
}
let Some(primary) = own.key(&policy.primary) else {
continue;
};
if let Some(j) = pick(&used, &|h| {
h.key(&policy.primary) == Some(primary) && tier(own, h)
}) {
partner[i] = Some(j);
joined_on[i] = Some(&policy.primary);
used[j] = true;
}
}
}
for (i, own) in a.halves.iter().enumerate() {
if partner[i].is_some() {
continue;
}
let Some(secondary) = own.key(&policy.secondary) else {
continue;
};
if let Some(j) = pick(&used, &|h| h.key(&policy.secondary) == Some(secondary)) {
partner[i] = Some(j);
joined_on[i] = Some(&policy.secondary);
used[j] = true;
}
}
let mut results = Vec::with_capacity(a.halves.len() + b.halves.len());
for (i, own) in a.halves.iter().enumerate() {
let Some(j) = partner[i] else {
let provable = own.covered && b.complete && !own.has_no_keys();
results.push(PairResult {
state: if provable {
PairState::AOnly
} else {
PairState::Insufficient
},
join_key: None,
a: Some(own.record_id.clone()),
b: None,
group: None,
});
continue;
};
let peer = &b.halves[j];
let key = joined_on[i].expect("a paired half records its join key");
let group = policy
.group
.as_deref()
.and_then(|g| own.key(g).filter(|v| peer.key(g) == Some(*v)))
.map(str::to_string);
let secondaries_disagree = matches!(
(own.key(&policy.secondary), peer.key(&policy.secondary)),
(Some(x), Some(y)) if x != y
);
let state = if key == policy.primary && secondaries_disagree {
PairState::Conflicting
} else if !own.covered || !peer.covered {
PairState::Insufficient
} else if !own.trusted || !peer.trusted {
PairState::Unresolved
} else if own.failed && peer.failed {
PairState::Matched
} else if own.failed != peer.failed {
PairState::Conflicting
} else if compare(own, peer) {
PairState::Matched
} else {
PairState::Conflicting
};
results.push(PairResult {
state,
join_key: Some(key.to_string()),
a: Some(own.record_id.clone()),
b: Some(peer.record_id.clone()),
group,
});
}
for (j, peer) in b.halves.iter().enumerate() {
if used[j] {
continue;
}
let provable = peer.covered && a.complete && !peer.has_no_keys();
results.push(PairResult {
state: if provable {
PairState::BOnly
} else {
PairState::Insufficient
},
join_key: None,
a: None,
b: Some(peer.record_id.clone()),
group: None,
});
}
let mut tallies = Tallies::default();
for r in &results {
tallies.add(r.state);
}
(results, tallies)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "SCREAMING_SNAKE_CASE")]
pub enum CloseStatus {
Agreed,
Unilateral,
Contested,
}
pub fn close_status<'a>(
close_id: &str,
counterparty_links: impl IntoIterator<Item = (LinkType, &'a str)>,
) -> CloseStatus {
let mut status = CloseStatus::Unilateral;
for (link_type, target) in counterparty_links {
if target != close_id {
continue;
}
match link_type {
LinkType::Rebuts => return CloseStatus::Contested,
LinkType::Acknowledges => status = CloseStatus::Agreed,
_ => {}
}
}
status
}
#[cfg(test)]
mod tests {
use super::*;
fn policy() -> JoinPolicy {
JoinPolicy {
primary: "k1".into(),
secondary: "k2".into(),
group: Some("g".into()),
}
}
fn keys(pairs: &[(&str, &str)]) -> BTreeMap<String, String> {
pairs
.iter()
.map(|(k, v)| (k.to_string(), v.to_string()))
.collect()
}
fn half(id: &str, correlation: &[(&str, &str)], payload: &str) -> Half {
Half {
record_id: id.into(),
seq: 1,
correlation: keys(correlation),
payload_commitments: vec![crate::canonical::json_digest(&payload.into()).unwrap()],
covered: true,
trusted: true,
failed: false,
}
}
fn failed(id: &str, correlation: &[(&str, &str)]) -> Half {
Half {
payload_commitments: Vec::new(),
failed: true,
..half(id, correlation, "")
}
}
fn by_pair(results: &[PairResult]) -> BTreeMap<String, PairState> {
results
.iter()
.map(|r| {
(
format!(
"{}|{}",
r.a.as_deref().unwrap_or(""),
r.b.as_deref().unwrap_or("")
),
r.state,
)
})
.collect()
}
#[test]
fn every_state_is_reachable_and_each_half_lands_in_exactly_one() {
let mut uncovered = half("a-uncovered", &[("k1", "x4")], "u");
uncovered.covered = false;
let mut untrusted = half("a-untrusted", &[("k1", "x5")], "t");
untrusted.trusted = false;
let a = HalfSet {
complete: true,
halves: vec![
half("a-matched", &[("k1", "x1")], "same"),
half("a-conflicting", &[("k1", "x2")], "mine"),
half("a-only", &[("k1", "x3")], "lonely"),
uncovered,
untrusted,
],
};
let b = HalfSet {
complete: true,
halves: vec![
half("b-matched", &[("k1", "x1")], "same"),
half("b-conflicting", &[("k1", "x2")], "theirs"),
half("b-uncovered-pair", &[("k1", "x4")], "p"),
half("b-untrusted-pair", &[("k1", "x5")], "q"),
half("b-only", &[("k1", "x6")], "alone"),
],
};
let (results, tallies) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(
tallies,
Tallies {
matched: 1,
a_only: 1,
b_only: 1,
conflicting: 1,
insufficient: 1,
unresolved: 1
}
);
let got = by_pair(&results);
for (pair, state) in [
("a-matched|b-matched", PairState::Matched),
("a-conflicting|b-conflicting", PairState::Conflicting),
("a-only|", PairState::AOnly),
("a-uncovered|b-uncovered-pair", PairState::Insufficient),
("a-untrusted|b-untrusted-pair", PairState::Unresolved),
("|b-only", PairState::BOnly),
] {
assert_eq!(got.get(pair), Some(&state), "{pair}: {results:?}");
}
}
#[test]
fn one_half_unavailable_is_not_disagreement() {
let disagree = |_: &Half, _: &Half| false;
for complete in [true, false] {
let a = HalfSet {
complete,
halves: vec![half("a1", &[("k2", "r1")], "x")],
};
let b = HalfSet {
complete,
halves: vec![half("b1", &[("k2", "r2")], "y")],
};
let (_, t) = reconcile_halves(&a, &b, &policy(), &disagree);
assert_eq!(t.conflicting, 0, "complete={complete}: {t:?}");
let only = usize::from(complete);
assert_eq!(
(t.a_only, t.b_only, t.insufficient),
(only, only, 2 - 2 * only)
);
}
}
#[test]
fn agreeing_primary_with_disagreeing_secondary_conflicts_and_is_not_repaired() {
let a = HalfSet {
complete: true,
halves: vec![half("a", &[("k1", "x"), ("k2", "r1")], "p")],
};
let b = HalfSet {
complete: true,
halves: vec![
half("b", &[("k1", "x"), ("k2", "r2")], "p"),
half("b-other", &[("k2", "r1")], "p"),
],
};
let (results, t) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(results[0].state, PairState::Conflicting);
assert_eq!(results[0].join_key.as_deref(), Some("k1"));
assert_eq!(results[0].b.as_deref(), Some("b"));
assert_eq!(t.b_only, 1, "b-other stays unpaired: {results:?}");
}
#[test]
fn primary_pass_prefers_a_counterpart_whose_secondary_agrees() {
let a = HalfSet {
complete: true,
halves: vec![half("a", &[("k1", "x"), ("k2", "r1")], "p")],
};
let b = HalfSet {
complete: true,
halves: vec![
half("b-wrong", &[("k1", "x"), ("k2", "r9")], "p"),
half("b-right", &[("k1", "x"), ("k2", "r1")], "p"),
],
};
let (results, _) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(results[0].b.as_deref(), Some("b-right"));
assert_eq!(results[0].state, PairState::Matched);
}
#[test]
fn secondary_joins_only_what_the_primary_left_unpaired() {
let a = HalfSet {
complete: true,
halves: vec![half("a", &[("k1", "x"), ("k2", "r1")], "p")],
};
let b = HalfSet {
complete: true,
halves: vec![half("b", &[("k1", "y"), ("k2", "r1")], "p")],
};
let (results, _) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(results.len(), 1);
assert_eq!(results[0].join_key.as_deref(), Some("k2"));
assert_eq!(results[0].state, PairState::Matched);
}
#[test]
fn the_group_key_is_recorded_when_shared_and_never_joins() {
let a = HalfSet {
complete: true,
halves: vec![
half("a1", &[("k1", "x"), ("g", "grp")], "p"),
half("a2", &[("g", "grp-2")], "p"),
],
};
let b = HalfSet {
complete: true,
halves: vec![
half("b1", &[("k1", "x"), ("g", "grp")], "p"),
half("b2", &[("g", "grp-2")], "p"),
],
};
let (results, t) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(results[0].group.as_deref(), Some("grp"));
assert_eq!(t.matched, 1);
assert_eq!((t.a_only, t.b_only), (1, 1), "{results:?}");
}
#[test]
fn the_group_key_is_not_recorded_unless_both_halves_carry_the_same_value() {
for peer_group in [None, Some("other")] {
let mut peer_keys = vec![("k1", "x")];
peer_keys.extend(peer_group.map(|g| ("g", g)));
let a = HalfSet {
complete: true,
halves: vec![half("a", &[("k1", "x"), ("g", "grp")], "p")],
};
let b = HalfSet {
complete: true,
halves: vec![half("b", &peer_keys, "p")],
};
let (results, _) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(results[0].state, PairState::Matched);
assert_eq!(results[0].group, None, "peer group {peer_group:?}");
}
}
#[test]
fn a_half_carrying_only_a_group_key_is_provably_absent_without_a_group_policy() {
let no_group = JoinPolicy {
group: None,
..policy()
};
let a = HalfSet {
complete: true,
halves: vec![half("a", &[("g", "grp")], "p")],
};
let (_, t) = reconcile_halves(
&a,
&HalfSet {
complete: true,
halves: vec![],
},
&no_group,
&same_payload_commitments,
);
assert_eq!((t.a_only, t.insufficient), (1, 0));
}
#[test]
fn a_half_with_no_keys_is_insufficient_even_against_a_complete_account() {
let a = HalfSet {
complete: true,
halves: vec![half("a", &[], "p")],
};
let b = HalfSet {
complete: true,
halves: vec![],
};
let (_, t) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(t.insufficient, 1);
assert_eq!(t.a_only, 0);
}
#[test]
fn failed_halves_pair_by_outcome_and_never_reach_the_content_test() {
let a = HalfSet {
complete: true,
halves: vec![
failed("a-402", &[("k1", "x1")]),
failed("a-timeout", &[("k1", "x2")]),
half("a-served", &[("k1", "x3"), ("k2", "d3")], "same"),
failed("a-alone", &[("k1", "x4")]),
],
};
let b = HalfSet {
complete: true,
halves: vec![
failed("b-402", &[("k1", "x1")]),
half("b-finished", &[("k1", "x2"), ("k2", "d2")], "done"),
failed("b-failed", &[("k1", "x3")]),
],
};
let never = |_: &Half, _: &Half| -> bool { panic!("content test ran on a failed half") };
let (results, tallies) = reconcile_halves(&a, &b, &policy(), &never);
assert_eq!(
tallies,
Tallies {
matched: 1,
conflicting: 2,
a_only: 1,
..Tallies::default()
}
);
let got = by_pair(&results);
for (pair, state) in [
("a-402|b-402", PairState::Matched),
("a-timeout|b-finished", PairState::Conflicting),
("a-served|b-failed", PairState::Conflicting),
("a-alone|", PairState::AOnly),
] {
assert_eq!(got.get(pair), Some(&state), "{pair}: {results:?}");
}
}
#[test]
fn a_failed_half_is_still_gated_by_coverage_and_trust() {
let mut uncovered = failed("a-uncovered", &[("k1", "x1")]);
uncovered.covered = false;
let mut untrusted = failed("a-untrusted", &[("k1", "x2")]);
untrusted.trusted = false;
let a = HalfSet {
complete: true,
halves: vec![uncovered, untrusted],
};
let b = HalfSet {
complete: true,
halves: vec![failed("b1", &[("k1", "x1")]), failed("b2", &[("k1", "x2")])],
};
let (_, tallies) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(
tallies,
Tallies {
insufficient: 1,
unresolved: 1,
..Tallies::default()
}
);
}
#[test]
fn a_failed_attempt_and_a_served_retry_pair_by_outcome() {
let served = |id: &str| half(id, &[("k1", "x1"), ("k2", "d1")], "same");
for b_halves in [
vec![failed("b-failed", &[("k1", "x1")]), served("b-served")],
vec![served("b-served"), failed("b-failed", &[("k1", "x1")])],
] {
let a = HalfSet {
complete: true,
halves: vec![served("a-served"), failed("a-failed", &[("k1", "x1")])],
};
let b = HalfSet {
complete: true,
halves: b_halves,
};
let (results, tallies) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
assert_eq!(
tallies,
Tallies {
matched: 2,
..Tallies::default()
},
"{results:?}"
);
let got = by_pair(&results);
assert_eq!(got.get("a-served|b-served"), Some(&PairState::Matched));
assert_eq!(got.get("a-failed|b-failed"), Some(&PairState::Matched));
}
}
#[test]
fn an_earlier_halfs_fallback_never_takes_a_later_halfs_better_partner() {
let a = HalfSet {
complete: true,
halves: vec![
half("a1", &[("k1", "x")], "same"),
half("a2", &[("k1", "x"), ("k2", "d1")], "same"),
],
};
let b = HalfSet {
complete: true,
halves: vec![
half("b1", &[("k1", "x"), ("k2", "d1")], "same"),
half("b2", &[("k1", "x"), ("k2", "d9")], "same"),
],
};
let (results, tallies) = reconcile_halves(&a, &b, &policy(), &same_payload_commitments);
let got = by_pair(&results);
assert_eq!(got.get("a2|b1"), Some(&PairState::Matched), "{results:?}");
assert_eq!(got.get("a1|b2"), Some(&PairState::Matched), "{results:?}");
assert_eq!(
tallies,
Tallies {
matched: 2,
..Tallies::default()
}
);
}
#[test]
fn a_key_conflict_outranks_two_failed_halves() {
let a = HalfSet {
complete: true,
halves: vec![failed("a", &[("k1", "x"), ("k2", "r1")])],
};
let b = HalfSet {
complete: true,
halves: vec![failed("b", &[("k1", "x"), ("k2", "r2")])],
};
let never = |_: &Half, _: &Half| -> bool { panic!("content test ran on a failed half") };
let (results, tallies) = reconcile_halves(&a, &b, &policy(), &never);
assert_eq!(by_pair(&results).get("a|b"), Some(&PairState::Conflicting));
assert_eq!(
tallies,
Tallies {
conflicting: 1,
..Tallies::default()
}
);
}
#[test]
fn tallies_serialize_under_the_state_tokens() {
let v = serde_json::to_value(Tallies::default()).unwrap();
for s in PairState::ALL {
let token = serde_json::to_value(s).unwrap();
assert!(v.get(token.as_str().unwrap()).is_some(), "{token}");
}
}
#[test]
fn close_status_reads_the_counterpartys_links() {
let id = "c".repeat(64);
let other = "d".repeat(64);
assert_eq!(close_status(&id, []), CloseStatus::Unilateral);
assert_eq!(
close_status(&id, [(LinkType::Acknowledges, other.as_str())]),
CloseStatus::Unilateral
);
assert_eq!(
close_status(&id, [(LinkType::Acknowledges, id.as_str())]),
CloseStatus::Agreed
);
assert_eq!(
close_status(
&id,
[
(LinkType::Acknowledges, id.as_str()),
(LinkType::Rebuts, id.as_str())
]
),
CloseStatus::Contested
);
assert_eq!(
close_status(&id, [(LinkType::Cites, id.as_str())]),
CloseStatus::Unilateral
);
}
}