runx-receipts 0.6.19

Pure Rust receipt model, canonicalization, and verification parity for runx.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

use std::collections::BTreeSet;

use runx_contracts::{Receipt, Reference, ReferenceType};

use super::{ReceiptResolveResult, ReceiptResolver, ReceiptTreeConfig};
use crate::tree::findings::{
    ambiguous_child, join, malformed_child_ref, missing_child, parent_link_findings, resolver_error,
};
use crate::tree::proof::ChildProofPolicy;
use crate::{ReceiptFinding, ReceiptFindingCode};

pub(super) struct TreeTraversal<'a, R: ReceiptResolver, P: ChildProofPolicy> {
    pub(super) resolver: &'a R,
    pub(super) config: ReceiptTreeConfig,
    pub(super) proof_policy: P,
    pub(super) visiting: BTreeSet<String>,
    pub(super) reached: BTreeSet<String>,
}

impl<R: ReceiptResolver, P: ChildProofPolicy> TreeTraversal<'_, R, P> {
    pub(super) fn subtree_findings(
        &mut self,
        path: &str,
        receipt: &Receipt,
        depth: usize,
    ) -> Vec<ReceiptFinding> {
        if !self.visiting.insert(receipt.id.to_string()) {
            return vec![ReceiptFinding {
                code: ReceiptFindingCode::ChildReceiptCycle,
                path: join(path, "id"),
                message: "child receipt refs must not form cycles".to_owned(),
            }];
        }

        let mut findings = Vec::new();
        let empty: Vec<Reference> = Vec::new();
        let child_refs = receipt
            .lineage
            .as_ref()
            .map_or(&empty, |lineage| &lineage.children);
        if child_refs.len() > self.config.max_breadth {
            findings.push(ReceiptFinding {
                code: ReceiptFindingCode::ChildReceiptBreadthLimit,
                path: join(path, "lineage.children"),
                message: "child receipt refs exceed configured breadth limit".to_owned(),
            });
        }

        let child_findings = child_refs
            .iter()
            .take(self.config.max_breadth)
            .enumerate()
            .flat_map(|(index, reference)| {
                self.child_ref_findings(
                    &join(path, &format!("lineage.children[{index}]")),
                    receipt,
                    reference,
                    depth,
                )
            })
            .collect::<Vec<_>>();
        findings.extend(child_findings);
        self.visiting.remove(receipt.id.as_str());
        findings
    }

    fn child_ref_findings(
        &mut self,
        path: &str,
        parent: &Receipt,
        reference: &Reference,
        depth: usize,
    ) -> Vec<ReceiptFinding> {
        if reference.reference_type != ReferenceType::Receipt {
            return vec![malformed_child_ref(path)];
        };
        let next_depth = depth.saturating_add(1);
        if next_depth > self.config.max_depth {
            return vec![ReceiptFinding {
                code: ReceiptFindingCode::ChildReceiptDepthLimit,
                path: path.to_owned(),
                message: "child receipt refs exceed configured depth limit".to_owned(),
            }];
        };
        let resolved = match self.resolver.resolve_child(reference) {
            ReceiptResolveResult::Found(resolved) => resolved,
            ReceiptResolveResult::Missing => return vec![missing_child(path)],
            ReceiptResolveResult::Malformed => return vec![malformed_child_ref(path)],
            ReceiptResolveResult::Ambiguous => return vec![ambiguous_child(path)],
            ReceiptResolveResult::ResolverError => return vec![resolver_error(path)],
        };
        let child = resolved.receipt;
        if self.visiting.contains(child.id.as_str()) {
            return vec![ReceiptFinding {
                code: ReceiptFindingCode::ChildReceiptCycle,
                path: path.to_owned(),
                message: "child receipt refs must not point to an ancestor".to_owned(),
            }];
        }
        let child_path = resolved.path.clone();
        let mut findings = self.proof_policy.findings(&resolved.path, reference, child);
        if self.reached.contains(child.id.as_str()) {
            return findings;
        }
        findings.extend(parent_link_findings(path, parent, child, self.config));
        findings.extend(self.subtree_findings(&child_path, child, next_depth));
        self.reached.insert(child.id.to_string());
        findings
    }
}