MCPcopy Create free account
hub / github.com/atomicdotdev/atomic / build

Method build

atomic-core/src/pristine/span_patch_storage.rs:550–614  ·  view source on GitHub ↗
(
        order: &[NodeId],
        dependencies: &HashMap<NodeId, Vec<NodeId>>,
        budget: usize,
    )

Source from the content-addressed store, hash-verified

548
549impl 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 }

Calls 6

iter_mutMethod · 0.80
getMethod · 0.65
lenMethod · 0.45
collectMethod · 0.45
iterMethod · 0.45
contextMethod · 0.45