runx_receipts/
tree.rs

1mod findings;
2mod proof;
3mod resolver;
4mod traversal;
5
6#[cfg(test)]
7mod proof_tests;
8#[cfg(test)]
9mod structural_tests;
10#[cfg(test)]
11mod test_support;
12
13use std::collections::BTreeSet;
14
15use runx_contracts::{Receipt, Reference};
16
17use crate::{
18    ReceiptFinding, ReceiptProofContext, ReceiptVerification, verify_receipt, verify_receipt_proof,
19};
20use findings::{child_receipt_findings, duplicate_child_findings, orphan_child_findings};
21use proof::{StrictChildProofPolicy, StructuralChildProofPolicy, child_receipt_proof_findings};
22use resolver::SliceReceiptResolver;
23use traversal::TreeTraversal;
24
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub struct ReceiptTreeConfig {
27    pub max_depth: usize,
28    pub max_breadth: usize,
29    pub require_parent_links: bool,
30}
31
32impl Default for ReceiptTreeConfig {
33    fn default() -> Self {
34        Self {
35            max_depth: 64,
36            max_breadth: 1024,
37            require_parent_links: false,
38        }
39    }
40}
41
42pub trait ReceiptResolver {
43    fn resolve_child<'a>(&'a self, reference: &Reference) -> ReceiptResolveResult<'a>;
44    fn supplied_receipts<'a>(&'a self) -> Vec<ResolvedReceipt<'a>>;
45}
46
47pub trait ReceiptProofContextProvider {
48    fn proof_context<'a>(&'a self, receipt: &Receipt) -> ReceiptProofContext<'a>;
49}
50
51#[derive(Clone, Debug)]
52pub struct ResolvedReceipt<'a> {
53    pub path: String,
54    pub receipt: &'a Receipt,
55}
56
57#[derive(Clone, Debug)]
58pub enum ReceiptResolveResult<'a> {
59    Found(ResolvedReceipt<'a>),
60    Missing,
61    Malformed,
62    Ambiguous,
63    ResolverError,
64}
65
66pub fn validate_receipt_tree(
67    root: &Receipt,
68    children: &[Receipt],
69) -> Result<(), ReceiptVerification> {
70    let resolver = SliceReceiptResolver { children };
71    validate_receipt_tree_with_resolver(root, &resolver, ReceiptTreeConfig::default())
72}
73
74#[must_use]
75pub fn verify_receipt_tree(root: &Receipt, children: &[Receipt]) -> ReceiptVerification {
76    let resolver = SliceReceiptResolver { children };
77    verify_receipt_tree_with_resolver(root, &resolver, ReceiptTreeConfig::default())
78}
79
80pub fn validate_receipt_tree_proof(
81    root: &Receipt,
82    children: &[Receipt],
83    proof_contexts: &impl ReceiptProofContextProvider,
84) -> Result<(), ReceiptVerification> {
85    let resolver = SliceReceiptResolver { children };
86    validate_receipt_tree_proof_with_resolver(
87        root,
88        &resolver,
89        ReceiptTreeConfig::default(),
90        proof_contexts,
91    )
92}
93
94#[must_use]
95pub fn verify_receipt_tree_proof(
96    root: &Receipt,
97    children: &[Receipt],
98    proof_contexts: &impl ReceiptProofContextProvider,
99) -> ReceiptVerification {
100    let resolver = SliceReceiptResolver { children };
101    verify_receipt_tree_proof_with_resolver(
102        root,
103        &resolver,
104        ReceiptTreeConfig::default(),
105        proof_contexts,
106    )
107}
108
109pub fn validate_receipt_tree_with_resolver(
110    root: &Receipt,
111    resolver: &impl ReceiptResolver,
112    config: ReceiptTreeConfig,
113) -> Result<(), ReceiptVerification> {
114    let verification = verify_receipt_tree_with_resolver(root, resolver, config);
115    if verification.valid {
116        Ok(())
117    } else {
118        Err(verification)
119    }
120}
121
122#[must_use]
123pub fn verify_receipt_tree_with_resolver(
124    root: &Receipt,
125    resolver: &impl ReceiptResolver,
126    config: ReceiptTreeConfig,
127) -> ReceiptVerification {
128    let mut findings = verify_receipt(root).findings;
129    let supplied = resolver.supplied_receipts();
130    findings.extend(duplicate_child_findings(&supplied));
131    findings.extend(child_receipt_findings(&supplied));
132    verify_tree_relationships(root, resolver, config, &supplied, findings)
133}
134
135pub fn validate_receipt_tree_proof_with_resolver(
136    root: &Receipt,
137    resolver: &impl ReceiptResolver,
138    config: ReceiptTreeConfig,
139    proof_contexts: &impl ReceiptProofContextProvider,
140) -> Result<(), ReceiptVerification> {
141    let verification =
142        verify_receipt_tree_proof_with_resolver(root, resolver, config, proof_contexts);
143    if verification.valid {
144        Ok(())
145    } else {
146        Err(verification)
147    }
148}
149
150#[must_use]
151pub fn verify_receipt_tree_proof_with_resolver(
152    root: &Receipt,
153    resolver: &impl ReceiptResolver,
154    config: ReceiptTreeConfig,
155    proof_contexts: &impl ReceiptProofContextProvider,
156) -> ReceiptVerification {
157    let root_context = proof_contexts.proof_context(root);
158    let mut findings = verify_receipt_proof(root, &root_context).findings;
159    let supplied = resolver.supplied_receipts();
160    findings.extend(duplicate_child_findings(&supplied));
161    findings.extend(child_receipt_proof_findings(&supplied, proof_contexts));
162    verify_tree_relationships_with_proof(
163        root,
164        resolver,
165        config,
166        &supplied,
167        findings,
168        proof_contexts,
169    )
170}
171
172fn verify_tree_relationships<R: ReceiptResolver>(
173    root: &Receipt,
174    resolver: &R,
175    config: ReceiptTreeConfig,
176    supplied: &[ResolvedReceipt<'_>],
177    mut findings: Vec<ReceiptFinding>,
178) -> ReceiptVerification {
179    let mut traversal = TreeTraversal {
180        resolver,
181        config,
182        proof_policy: StructuralChildProofPolicy,
183        visiting: BTreeSet::new(),
184        reached: BTreeSet::new(),
185    };
186    findings.extend(traversal.subtree_findings("", root, 0));
187    findings.extend(orphan_child_findings(supplied, &traversal.reached));
188    ReceiptVerification::from_findings(findings)
189}
190
191fn verify_tree_relationships_with_proof<R: ReceiptResolver>(
192    root: &Receipt,
193    resolver: &R,
194    config: ReceiptTreeConfig,
195    supplied: &[ResolvedReceipt<'_>],
196    mut findings: Vec<ReceiptFinding>,
197    proof_contexts: &impl ReceiptProofContextProvider,
198) -> ReceiptVerification {
199    let mut traversal = TreeTraversal {
200        resolver,
201        config,
202        proof_policy: StrictChildProofPolicy::new(supplied, proof_contexts),
203        visiting: BTreeSet::new(),
204        reached: BTreeSet::new(),
205    };
206    findings.extend(traversal.subtree_findings("", root, 0));
207    findings.extend(orphan_child_findings(supplied, &traversal.reached));
208    ReceiptVerification::from_findings(findings)
209}
runx_receipts/tree.rs

runx_receipts/
tree.rs
