causal.rs (11491B)
1 use super::agreement::{buyer, group, line, money, seller, terms}; 2 use radroots_domain::{causal::*, *}; 3 #[path = "terms_authorization.rs"] 4 mod terms_authorization; 5 6 fn id(value: u64) -> RecordId { 7 let mut out = [0; 32]; 8 out[24..].copy_from_slice(&value.to_be_bytes()); 9 RecordId::from_bytes(out) 10 } 11 fn src(value: u64) -> SourceId { 12 SourceId::from_bytes(id(value).into_bytes()) 13 } 14 fn order() -> OrderId { 15 OrderId::from_bytes([2; 32]) 16 } 17 fn thread() -> ThreadId { 18 ThreadId::from_bytes([1; 32]) 19 } 20 fn scope() -> CausalScope { 21 CausalScope::new(thread(), order(), buyer(), seller()).unwrap() 22 } 23 fn make(author: PublicKey, sequence: u64, previous: Option<u64>, extra: &[u64]) -> CommerceContent { 24 let mut parents = vec![src(9000)]; 25 parents.extend(previous.map(src)); 26 parents.extend(extra.iter().copied().map(src)); 27 parents.sort(); 28 parents.dedup(); 29 let header = CommerceHeader::new( 30 thread(), 31 Some(order()), 32 author, 33 buyer(), 34 seller(), 35 UnixSeconds::new(100).unwrap(), 36 Sequence::new(sequence).unwrap(), 37 previous.map(id), 38 parents, 39 ) 40 .unwrap(); 41 let reason = RecordReason::new(id(9000), "private reason").unwrap(); 42 let payload = if author == seller() { 43 CommercePayload::Decline(reason) 44 } else { 45 CommercePayload::WithdrawalRequested(reason) 46 }; 47 CommerceContent::new(header, payload).unwrap() 48 } 49 fn evaluate( 50 values: &[(u64, CommerceContent)], 51 external: &[u64], 52 uninterpreted: &[u64], 53 ) -> CausalAnalysis { 54 analyze( 55 scope(), 56 &values 57 .iter() 58 .map(|(identity, content)| CausalRecord::new(id(*identity), content)) 59 .collect::<Vec<_>>(), 60 &external.iter().copied().map(src).collect::<Vec<_>>(), 61 &uninterpreted.iter().copied().map(src).collect::<Vec<_>>(), 62 ) 63 .unwrap() 64 } 65 66 #[test] 67 fn every_arrival_order_and_exact_duplicates_preserve_both_complete_author_heads() { 68 let values = [ 69 (1, make(seller(), 1, None, &[])), 70 (2, make(buyer(), 1, None, &[1])), 71 (3, make(seller(), 2, Some(1), &[2])), 72 (4, make(buyer(), 2, Some(2), &[3])), 73 ]; 74 let expected = evaluate(&values, &[9000], &[]); 75 assert_eq!(expected.readiness(), CausalReadiness::Complete); 76 assert_eq!(expected.seller_head(), Some(id(3))); 77 assert_eq!(expected.buyer_head(), Some(id(4))); 78 assert_eq!(expected.quote_head(), None); 79 for a in 0..4 { 80 for b in 0..4 { 81 for c in 0..4 { 82 for d in 0..4 { 83 let indices = [a, b, c, d]; 84 if (0..4).any(|i| indices[..i].contains(&indices[i])) { 85 continue; 86 } 87 let shuffled = indices.map(|i| values[i].clone()); 88 assert_eq!(evaluate(&shuffled, &[9000], &[]), expected); 89 let duplicated = [shuffled.as_slice(), &shuffled[..2]].concat(); 90 assert_eq!(evaluate(&duplicated, &[9000], &[]), expected); 91 } 92 } 93 } 94 } 95 assert!(!expected.has_cycle()); 96 assert!(expected.missing().is_empty()); 97 assert!(expected.conflicts().is_empty()); 98 } 99 100 #[test] 101 fn exact_missing_predecessors_cannot_be_satisfied_by_generic_sources_or_empty_history() { 102 let values = [(2, make(buyer(), 2, Some(1), &[5, 6]))]; 103 let result = evaluate(&values, &[9000, 1, 5], &[]); 104 assert_eq!(result.readiness(), CausalReadiness::MissingHistory); 105 assert_eq!(result.missing(), [src(1), src(6)]); 106 assert_eq!(result.buyer_head(), None); 107 assert!(!result.has_cycle()); 108 let result = evaluate(&values, &[9000], &[1]); 109 assert_eq!(result.readiness(), CausalReadiness::Uninterpreted); 110 assert!(result.missing().contains(&src(1))); 111 let empty = evaluate(&[], &[], &[]); 112 assert_eq!(empty.readiness(), CausalReadiness::Complete); 113 assert_eq!(empty.buyer_head(), None); 114 // Complete describes only supplied coverage; it cannot invent a request. 115 } 116 117 #[test] 118 fn incompatible_same_sequence_records_expose_all_forks_and_retain_only_the_uncontested_prefix() { 119 let values = [ 120 (1, make(seller(), 1, None, &[])), 121 (2, make(seller(), 2, Some(1), &[])), 122 (3, make(seller(), 2, Some(1), &[20])), 123 (4, make(seller(), 3, Some(2), &[])), 124 (5, make(seller(), 2, Some(1), &[21])), 125 ]; 126 let expected = evaluate(&values, &[9000, 20, 21], &[]); 127 assert_eq!(expected.readiness(), CausalReadiness::Conflicted); 128 assert_eq!(expected.seller_head(), Some(id(1))); 129 assert_eq!(expected.conflicts(), [id(2), id(3), id(5)]); 130 assert!(!expected.has_cycle()); 131 for rotation in 0..values.len() { 132 let mut reversed = values.to_vec(); 133 reversed.rotate_left(rotation); 134 reversed.reverse(); 135 assert_eq!(evaluate(&reversed, &[9000, 21, 20], &[]), expected); 136 } 137 } 138 139 #[test] 140 fn predecessor_author_and_sequence_mismatches_block_contiguous_heads() { 141 for values in [ 142 vec![ 143 (1, make(seller(), 1, None, &[])), 144 (2, make(buyer(), 2, Some(1), &[])), 145 ], 146 vec![ 147 (1, make(seller(), 1, None, &[])), 148 (2, make(seller(), 3, Some(1), &[])), 149 ], 150 ] { 151 let result = evaluate(&values, &[9000], &[]); 152 assert_eq!(result.readiness(), CausalReadiness::Conflicted); 153 assert_eq!(result.conflicts(), [id(2)]); 154 assert_eq!(result.buyer_head(), None); 155 assert_eq!(result.seller_head(), Some(id(1))); 156 } 157 } 158 159 #[test] 160 fn cross_author_cycles_and_descendants_are_bounded_and_never_timestamp_ranked() { 161 let values = [ 162 (1, make(seller(), 1, None, &[2])), 163 (2, make(buyer(), 1, None, &[1])), 164 (3, make(buyer(), 2, Some(2), &[])), 165 ]; 166 let result = evaluate(&values, &[9000], &[]); 167 assert_eq!(result.readiness(), CausalReadiness::Conflicted); 168 assert!(result.has_cycle()); 169 assert_eq!(result.conflicts(), [id(1), id(2), id(3)]); 170 assert_eq!(result.buyer_head(), None); 171 assert_eq!(result.seller_head(), None); 172 let missing_only = evaluate(&[(1, make(seller(), 1, None, &[2]))], &[9000], &[]); 173 assert!(!missing_only.has_cycle()); 174 assert_eq!(missing_only.readiness(), CausalReadiness::MissingHistory); 175 } 176 177 #[test] 178 fn authenticated_uninterpreted_evidence_blocks_reduction_even_when_not_referenced_by_known_nodes() { 179 let values = [(1, make(seller(), 1, None, &[]))]; 180 let result = evaluate(&values, &[9000, 44], &[44, 43, 44]); 181 assert_eq!(result.readiness(), CausalReadiness::Uninterpreted); 182 assert_eq!(result.uninterpreted(), [src(43), src(44)]); 183 assert!(result.missing().is_empty()); 184 assert_eq!(result.seller_head(), Some(id(1))); 185 } 186 187 fn quote(sequence: u64, previous: Option<u64>) -> CommerceContent { 188 let mut parents = vec![SourceId::from_bytes([3; 32])]; 189 parents.extend(previous.map(src)); 190 parents.sort(); 191 let header = CommerceHeader::new( 192 thread(), 193 None, 194 seller(), 195 buyer(), 196 seller(), 197 UnixSeconds::new(100).unwrap(), 198 Sequence::new(sequence).unwrap(), 199 previous.map(id), 200 parents, 201 ) 202 .unwrap(); 203 let complete = terms(vec![line(7, 9)], vec![group(9)], money("50"), money("700")).unwrap(); 204 CommerceContent::new( 205 header, 206 CommercePayload::Quote(TermsQuote::new( 207 complete, 208 UnixSeconds::new(200).unwrap(), 209 None, 210 )), 211 ) 212 .unwrap() 213 } 214 #[test] 215 fn null_order_quote_chains_remain_separate_from_the_same_seller_order_chain() { 216 let values = [ 217 (1, quote(1, None)), 218 (2, quote(2, Some(1))), 219 (3, make(seller(), 1, None, &[2])), 220 ]; 221 let external = [src(9000), SourceId::from_bytes([3; 32])]; 222 let records = values 223 .iter() 224 .map(|(i, c)| CausalRecord::new(id(*i), c)) 225 .collect::<Vec<_>>(); 226 let result = analyze(scope(), &records, &external, &[]).unwrap(); 227 assert_eq!(result.readiness(), CausalReadiness::Complete); 228 assert_eq!(result.quote_head(), Some(id(2))); 229 assert_eq!(result.seller_head(), Some(id(3))); 230 let bad = make(seller(), 3, Some(2), &[]); 231 let mut records = records; 232 records.push(CausalRecord::new(id(4), &bad)); 233 let result = analyze(scope(), &records, &external, &[]).unwrap(); 234 assert_eq!(result.readiness(), CausalReadiness::Conflicted); 235 assert!(result.conflicts().contains(&id(4))); 236 } 237 238 #[test] 239 fn mixed_scope_and_same_identity_changed_complete_payload_are_explicit_errors() { 240 let first = make(seller(), 1, None, &[]); 241 let second = make(seller(), 1, None, &[22]); 242 assert_eq!( 243 analyze( 244 scope(), 245 &[ 246 CausalRecord::new(id(1), &first), 247 CausalRecord::new(id(1), &second) 248 ], 249 &[src(9000), src(22)], 250 &[] 251 ) 252 .unwrap_err(), 253 CausalError::IdentityConflict 254 ); 255 for different in [ 256 CausalScope::new(ThreadId::from_bytes([9; 32]), order(), buyer(), seller()).unwrap(), 257 CausalScope::new(thread(), OrderId::from_bytes([9; 32]), buyer(), seller()).unwrap(), 258 CausalScope::new(thread(), order(), seller(), buyer()).unwrap(), 259 ] { 260 assert_eq!( 261 analyze(different, &[CausalRecord::new(id(1), &first)], &[], &[]).unwrap_err(), 262 CausalError::InvalidScope 263 ); 264 } 265 assert_eq!( 266 CausalScope::new(thread(), order(), seller(), seller()), 267 Err(CausalError::InvalidScope) 268 ); 269 } 270 271 #[test] 272 fn maximum_reverse_dependency_chain_is_iterative_and_limits_never_silently_truncate() { 273 assert_eq!(MAX_CAUSAL_RECORDS, 1000); 274 assert_eq!(MAX_CAUSAL_SOURCES, 8000); 275 let values = (1..=MAX_CAUSAL_RECORDS as u64) 276 .map(|sequence| { 277 ( 278 1001 - sequence, 279 make( 280 seller(), 281 sequence, 282 (sequence > 1).then_some(1002 - sequence), 283 &[], 284 ), 285 ) 286 }) 287 .collect::<Vec<_>>(); 288 let result = evaluate(&values, &[9000], &[]); 289 assert_eq!(result.readiness(), CausalReadiness::Complete); 290 assert_eq!(result.seller_head(), Some(id(1))); 291 let records = values 292 .iter() 293 .map(|(i, c)| CausalRecord::new(id(*i), c)) 294 .collect::<Vec<_>>(); 295 let mut excess = records.clone(); 296 excess.push(records[0]); 297 assert_eq!( 298 analyze(scope(), &excess, &[src(9000)], &[]).unwrap_err(), 299 CausalError::LimitExceeded 300 ); 301 for (external, uninterpreted) in [(vec![src(9); 8001], vec![]), (vec![], vec![src(9); 8001])] { 302 assert_eq!( 303 analyze(scope(), &records, &external, &uninterpreted).unwrap_err(), 304 CausalError::LimitExceeded 305 ); 306 } 307 } 308 309 #[test] 310 fn diagnostics_do_not_copy_private_contents_or_claim_permission() { 311 let content = make(seller(), 1, None, &[]); 312 let record = CausalRecord::new(id(1), &content); 313 assert_eq!(format!("{record:?}"), "CausalRecord(<untrusted claim>)"); 314 let result = analyze(scope(), &[record], &[src(9000)], &[]).unwrap(); 315 assert_eq!(format!("{result:?}"), "CausalAnalysis(<private coverage>)"); 316 for error in [ 317 CausalError::InvalidScope, 318 CausalError::IdentityConflict, 319 CausalError::LimitExceeded, 320 ] { 321 assert!(error.to_string().len() < 64); 322 assert!(core::error::Error::source(&error).is_none()); 323 } 324 }