Skip to main content

qualia_core_db/bundle/stream/proof/
builder.rs

1use super::{empty_root, hash::parent, leaf_hash, ProofError, TreeSpec, MAX_SIBLINGS};
2use crate::net::qdnf::types::StrongDigest;
3
4#[derive(Clone, Copy, Debug, PartialEq, Eq)]
5pub struct OutboardNode {
6    pub start_leaf: u64,
7    pub leaf_count: u64,
8    pub digest: StrongDigest,
9}
10
11/// Fixed-memory sequential builder. A failed or panicking observer poisons the
12/// builder: no root can subsequently be obtained. Sink durability/commit remains
13/// a separate publication gate; emitted nodes are only candidate digests.
14pub struct TreeBuilder {
15    spec: TreeSpec,
16    count: u64,
17    frontier: [StrongDigest; MAX_SIBLINGS + 1],
18    poisoned: bool,
19    finished: Option<StrongDigest>,
20}
21impl TreeBuilder {
22    pub fn new(spec: TreeSpec) -> Self {
23        Self {
24            spec,
25            count: 0,
26            frontier: [StrongDigest::ZERO; MAX_SIBLINGS + 1],
27            poisoned: false,
28            finished: None,
29        }
30    }
31    pub const fn appended(&self) -> u64 {
32        self.count
33    }
34    pub const fn is_poisoned(&self) -> bool {
35        self.poisoned
36    }
37    pub fn append(
38        &mut self,
39        bytes: &[u8],
40        mut observe: impl FnMut(OutboardNode) -> Result<(), ProofError>,
41    ) -> Result<(), ProofError> {
42        if self.poisoned {
43            return Err(ProofError::Poisoned);
44        }
45        if self.count == self.spec.leaf_count() {
46            return Err(ProofError::Complete);
47        }
48        let mut digest = leaf_hash(&self.spec, self.count, bytes)?;
49        let mut level = 0;
50        let mut width = 1u64;
51        self.poisoned = true;
52        observe(OutboardNode {
53            start_leaf: self.count,
54            leaf_count: width,
55            digest,
56        })
57        .map_err(|_| ProofError::Sink)?;
58        while self.count & width != 0 {
59            digest = parent(self.frontier[level], digest);
60            level += 1;
61            width <<= 1;
62            observe(OutboardNode {
63                start_leaf: self.count + 1 - width,
64                leaf_count: width,
65                digest,
66            })
67            .map_err(|_| ProofError::Sink)?;
68        }
69        self.frontier[level] = digest;
70        self.count += 1;
71        self.poisoned = false;
72        Ok(())
73    }
74    pub fn finish(
75        &mut self,
76        mut observe: impl FnMut(OutboardNode) -> Result<(), ProofError>,
77    ) -> Result<StrongDigest, ProofError> {
78        if self.poisoned {
79            return Err(ProofError::Poisoned);
80        }
81        if let Some(root) = self.finished {
82            return Ok(root);
83        }
84        if self.count != self.spec.leaf_count() {
85            return Err(ProofError::Incomplete);
86        }
87        if self.count == 0 {
88            let root = empty_root(&self.spec)?;
89            self.finished = Some(root);
90            return Ok(root);
91        }
92        self.poisoned = true;
93        let mut result = None;
94        let mut right_count = 0u64;
95        for level in 0..=MAX_SIBLINGS {
96            let width = 1u64 << level;
97            if self.count & width == 0 {
98                continue;
99            }
100            let digest = match result {
101                None => self.frontier[level],
102                Some(right) => parent(self.frontier[level], right),
103            };
104            if result.is_some() {
105                observe(OutboardNode {
106                    start_leaf: self.count - right_count - width,
107                    leaf_count: right_count + width,
108                    digest,
109                })
110                .map_err(|_| ProofError::Sink)?;
111            }
112            result = Some(digest);
113            right_count += width;
114        }
115        let root = result.ok_or(ProofError::Incomplete)?;
116        self.finished = Some(root);
117        self.poisoned = false;
118        Ok(root)
119    }
120}