zerokit_utils 1.2.0

Various utilities for Zerokit
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
111
112
113
114
115
116

use super::error::ZerokitMerkleTreeError;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct OverrideRangeValidation {
    pub indices: Vec<usize>,
    pub max_index: Option<usize>,
    pub min_index: Option<usize>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EmptyIndicesPolicy {
    Allow,
    Reject,
}

/// Validates and normalizes `override_range` inputs.
///
/// `start + leaves_len` is checked with `checked_add` to prevent overflow and
/// all indices are normalized (sorted and deduplicated) before use.
pub fn validate_override_range_inputs(
    start: usize,
    leaves_len: usize,
    mut indices: Vec<usize>,
    capacity: usize,
    empty_indices_policy: EmptyIndicesPolicy,
) -> Result<OverrideRangeValidation, ZerokitMerkleTreeError> {
    if matches!(empty_indices_policy, EmptyIndicesPolicy::Reject) && indices.is_empty() {
        return Err(ZerokitMerkleTreeError::InvalidIndices);
    }

    if indices.iter().any(|&i| i >= capacity) {
        return Err(ZerokitMerkleTreeError::InvalidIndices);
    }

    indices.sort_unstable();
    indices.dedup();

    let min_index = indices.first().copied();

    let max_index = if leaves_len == 0 {
        None
    } else {
        let end = start
            .checked_add(leaves_len)
            .ok_or(ZerokitMerkleTreeError::TooManySet)?;
        if end > capacity {
            return Err(ZerokitMerkleTreeError::TooManySet);
        }
        Some(end)
    };

    if let (Some(min_idx), Some(end)) = (min_index, max_index) {
        // Current override implementations build offsets with `start - min_index`,
        // so indices that begin after `start` are invalid for this flow.
        if min_idx > start || min_idx >= end {
            return Err(ZerokitMerkleTreeError::InvalidIndices);
        }
    }

    Ok(OverrideRangeValidation {
        indices,
        max_index,
        min_index,
    })
}

#[cfg(test)]
mod tests {
    use super::{validate_override_range_inputs, EmptyIndicesPolicy};
    use crate::merkle_tree::ZerokitMerkleTreeError;

    #[test]
    fn test_validate_override_range_inputs_accepts_valid_inputs() {
        // indices [0,1] are before start=2, leaves cover [2..=4] (indices 2,3,4), all within capacity
        let validated = validate_override_range_inputs(
            2,
            3,
            vec![1, 0],
            1usize << 20,
            EmptyIndicesPolicy::Allow,
        )
        .unwrap();
        assert_eq!(validated.min_index, Some(0));
        assert_eq!(validated.max_index, Some(5)); // start + leaves_len
        assert_eq!(validated.indices, vec![0, 1]); // sorted
    }

    #[test]
    fn test_validate_override_range_inputs_rejects_start_add_overflow() {
        let err = validate_override_range_inputs(
            usize::MAX,
            1,
            vec![0],
            1usize << 20,
            EmptyIndicesPolicy::Allow,
        )
        .unwrap_err();
        assert!(matches!(err, ZerokitMerkleTreeError::TooManySet));
    }

    #[test]
    fn test_validate_override_range_inputs_rejects_incompatible_mixed_offsets() {
        let err =
            validate_override_range_inputs(0, 2, vec![1], 1usize << 20, EmptyIndicesPolicy::Allow)
                .unwrap_err();
        assert!(matches!(err, ZerokitMerkleTreeError::InvalidIndices));
    }

    #[test]
    fn test_validate_override_range_inputs_rejects_empty_indices_when_required() {
        let err =
            validate_override_range_inputs(0, 1, vec![], 1usize << 20, EmptyIndicesPolicy::Reject)
                .unwrap_err();
        assert!(matches!(err, ZerokitMerkleTreeError::InvalidIndices));
    }
}