| 548 | |
| 549 | impl CausalProof { |
| 550 | fn build( |
| 551 | order: &[NodeId], |
| 552 | dependencies: &HashMap<NodeId, Vec<NodeId>>, |
| 553 | budget: usize, |
| 554 | ) -> Result<Option<Self>> { |
| 555 | if budget == 0 { |
| 556 | return Ok(None); |
| 557 | } |
| 558 | let count = order.len(); |
| 559 | let words = count.div_ceil(64); |
| 560 | let Some(cells) = count.checked_mul(words) else { |
| 561 | return Ok(None); |
| 562 | }; |
| 563 | let Some(bytes) = cells.checked_mul(8).and_then(|size| { |
| 564 | count |
| 565 | .checked_mul(std::mem::size_of::<(NodeId, usize)>()) |
| 566 | .and_then(|ranks| size.checked_add(ranks)) |
| 567 | }) else { |
| 568 | return Ok(None); |
| 569 | }; |
| 570 | if bytes > budget.min(MAX_PROOF_BYTES) { |
| 571 | return Ok(None); |
| 572 | } |
| 573 | let mut ranks: Vec<_> = order |
| 574 | .iter() |
| 575 | .enumerate() |
| 576 | .map(|(rank, &id)| (id, rank)) |
| 577 | .collect(); |
| 578 | ranks.sort_unstable_by_key(|(id, _)| id.get()); |
| 579 | ensure!( |
| 580 | ranks.windows(2).all(|pair| pair[0].0 != pair[1].0), |
| 581 | "duplicate visible change in span causal proof" |
| 582 | ); |
| 583 | let mut bits = Vec::new(); |
| 584 | if bits.try_reserve_exact(cells).is_err() { |
| 585 | return Ok(None); |
| 586 | } |
| 587 | bits.resize(cells, 0u64); |
| 588 | for (rank, &id) in order.iter().enumerate() { |
| 589 | let (earlier, rest) = bits.split_at_mut(rank * words); |
| 590 | let row = &mut rest[..words]; |
| 591 | row[rank / 64] |= 1u64 << (rank % 64); |
| 592 | for dep_id in dependencies |
| 593 | .get(&id) |
| 594 | .context("span causal proof dependencies missing")? |
| 595 | { |
| 596 | let index = ranks |
| 597 | .binary_search_by_key(&dep_id.get(), |(id, _)| id.get()) |
| 598 | .map_err(|_| anyhow::anyhow!("span causal proof closure is incomplete"))?; |
| 599 | let dep_rank = ranks[index].1; |
| 600 | ensure!(dep_rank < rank, "span causal proof is not dependency-first"); |
| 601 | for (word, previous) in row |
| 602 | .iter_mut() |
| 603 | .zip(&earlier[dep_rank * words..(dep_rank + 1) * words]) |
| 604 | { |
| 605 | *word |= *previous; |
| 606 | } |
| 607 | } |