eth_state_diff/

inactivity_scores.rs

//! Delta encoding for validator inactivity scores.
//!
//! Inactivity scores are represented as a vector indexed by validator index.
//! This module encodes changes between two score vectors without storing the
//! complete target vector.
//!
//! Two representations are supported:
//!
//! - A sparse representation containing only changed indices and their target
//!   values.
//! - An all-zero representation for transitions to a completely zero-valued
//!   target vector.
//!
//! Newly added validator scores are stored separately as an extension.
//!
//! Deltas produced by [`diff_inactivity`] can be applied in place using
//! [`apply_inactivity`].

use crate::{
    types::{ArchivedInactivityDiff, InactivityDiff},
    Error,
};

/// Computes a compact delta between two validator inactivity-score vectors.
///
/// The returned delta contains sufficient information to reconstruct `target`
/// from `base`.
///
/// If the target contains only zero-valued scores and the base contains at
/// least one non-zero score, [`InactivityDiff::AllZeros`] is emitted. This
/// avoids storing individual updates when the entire target vector has been
/// cleared.
///
/// Otherwise, [`InactivityDiff::Sparse`] stores only the indices whose values
/// changed and their corresponding target values. Scores belonging to newly
/// appended validators are stored in the `extensions` field.
///
/// If `base` and `target` have different lengths, only their common prefix is
/// compared. Any remaining target scores are treated as newly appended
/// entries.
///
/// # Arguments
///
/// * `base` - Inactivity scores from the source state.
/// * `target` - Inactivity scores from the target state.
///
/// # Returns
///
/// A compact [`InactivityDiff`] representing the transition from `base` to
/// `target`.
///
/// # Complexity
///
/// O(n) time, where *n* is the length of the larger input vector.
///
/// Additional space is proportional to the number of changed scores plus the
/// number of newly appended scores.
///
/// # Example
///
/// ```
/// use eth_state_diff::inactivity_scores::diff_inactivity;
/// use eth_state_diff::types::InactivityDiff;
///
/// let base = vec![10, 20, 30, 40];
/// let target = vec![10, 25, 30, 50];
///
/// let delta = diff_inactivity(&base, &target);
///
/// assert_eq!(
///     delta,
///     InactivityDiff::Sparse {
///         indices: vec![1, 3],
///         new_values: vec![25, 50],
///         extensions: vec![],
///     }
/// );
/// ```
///
/// A completely cleared vector can be represented without storing individual
/// zero values:
///
/// ```
/// use eth_state_diff::inactivity_scores::diff_inactivity;
/// use eth_state_diff::types::InactivityDiff;
///
/// let base = vec![10, 20, 30];
/// let target = vec![0, 0, 0];
///
/// assert_eq!(
///     diff_inactivity(&base, &target),
///     InactivityDiff::AllZeros(3)
/// );
/// ```
pub fn diff_inactivity(base: &[u64], target: &[u64]) -> InactivityDiff {
    let target_is_zero = target.iter().all(|&v| v == 0);

    if target_is_zero {
        let base_has_non_zero = base.iter().any(|&v| v != 0);

        if base_has_non_zero {
            let len =
                u32::try_from(target.len()).expect("inactivity-score vector length exceeds u32");
            return InactivityDiff::AllZeros(len);
        }
    }

    let common_len = base.len().min(target.len());
    let mut indices = Vec::with_capacity(100);
    let mut new_values = Vec::with_capacity(100);

    for (i, (&v1, &v2)) in base.iter().zip(target.iter()).take(common_len).enumerate() {
        if v1 != v2 {
            let idx = u32::try_from(i).expect("inactivity-score index exceeds u32");
            indices.push(idx);
            new_values.push(v2);
        }
    }

    let extensions = target
        .get(common_len..)
        .expect("common_len is bounded by target length")
        .to_vec();

    InactivityDiff::Sparse {
        indices,
        new_values,
        extensions,
    }
}

/// Applies an inactivity-score delta to a vector in place.
///
/// After successful execution, `base` contains the inactivity-score vector
/// represented by `delta`.
///
/// [`ArchivedInactivityDiff::AllZeros`] clears the existing vector and
/// recreates it with the specified number of zero-valued scores.
///
/// [`ArchivedInactivityDiff::Sparse`] updates the recorded indices and then
/// appends any newly added validator scores.
///
/// # Errors
///
/// Returns [`Error::InvalidDelta`] if:
///
/// - an all-zero vector length cannot be represented as a `usize`;
/// - the sparse index and value arrays have different lengths; or
/// - a sparse index is outside the current `base` vector.
///
/// A sparse delta must therefore be applied to a compatible base state.
///
/// # Complexity
///
/// - [`ArchivedInactivityDiff::AllZeros`]: O(n), where *n* is the target
///   vector length.
/// - [`ArchivedInactivityDiff::Sparse`]: O(m + k), where *m* is the number of
///   recorded updates and *k* is the number of appended scores.
///
/// # Example
///
/// ```
/// use eth_state_diff::inactivity_scores::{apply_inactivity, diff_inactivity};
/// use eth_state_diff::types::ArchivedInactivityDiff;
///
/// let mut base = vec![10, 20, 30];
/// let target = vec![10, 25, 30];
///
/// let delta = diff_inactivity(&base, &target);
///
/// let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta)
///     .expect("serializing a locally constructed delta should succeed");
/// let archived = rkyv::access::<ArchivedInactivityDiff, rkyv::rancor::Error>(&bytes)
///     .expect("test setup: failed to access archived delta");
///
/// apply_inactivity(&mut base, archived)
///     .expect("delta generated from the same base should apply successfully");
///
/// assert_eq!(base, target);
/// ```
pub fn apply_inactivity(base: &mut Vec<u64>, delta: &ArchivedInactivityDiff) -> Result<(), Error> {
    match delta {
        ArchivedInactivityDiff::AllZeros(len) => {
            let len = usize::try_from(len.to_native()).map_err(|_| {
                Error::InvalidDelta("inactivity-score vector length does not fit in usize".into())
            })?;

            base.clear();
            base.resize(len, 0);
        }

        ArchivedInactivityDiff::Sparse {
            indices,
            new_values,
            extensions,
        } => {
            if indices.len() != new_values.len() {
                return Err(Error::InvalidDelta(format!(
                    "inactivity-score delta contains {} indices but {} replacement values",
                    indices.len(),
                    new_values.len()
                )));
            }

            for (idx, val) in indices.iter().zip(new_values.iter()) {
                let index = usize::try_from(idx.to_native()).map_err(|_| {
                    Error::InvalidDelta("inactivity-score index does not fit in usize".into())
                })?;

                let Some(value) = base.get_mut(index) else {
                    return Err(Error::InvalidDelta(format!(
                        "inactivity-score index {index} is outside base vector of length {}",
                        base.len()
                    )));
                };

                *value = val.to_native();
            }

            base.reserve(extensions.len());
            base.extend(extensions.iter().map(|value| value.to_native()));
        }
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::ArchivedInactivityDiff;

    #[test]
    fn test_diff_all_zeros_fast_path() {
        let base = vec![10, 20, 30];
        let target = vec![0, 0, 0];

        let delta = diff_inactivity(&base, &target);

        assert!(matches!(delta, InactivityDiff::AllZeros(3)));
    }

    #[test]
    fn test_diff_sparse_identical() {
        let base = vec![10, 20, 30];
        let target = vec![10, 20, 30];

        let delta = diff_inactivity(&base, &target);

        match delta {
            InactivityDiff::Sparse {
                indices,
                new_values,
                extensions,
            } => {
                assert!(indices.is_empty());
                assert!(new_values.is_empty());
                assert!(extensions.is_empty());
            }
            _ => panic!("test setup: expected Sparse"),
        }
    }

    #[test]
    fn test_sparse_with_changes_and_extensions() {
        let base = vec![10, 20, 30, 40];
        let target = vec![10, 25, 30, 50, 60];
        // Changes at index 1 (20 -> 25) and index 3 (40 -> 50)

        let delta = diff_inactivity(&base, &target);

        match delta {
            InactivityDiff::Sparse {
                indices,
                new_values,
                extensions,
            } => {
                assert_eq!(*indices, [1u32, 3u32]);
                assert_eq!(*new_values, [25u64, 50u64]);
                assert_eq!(*extensions, [60u64]); // Fixed!
            }
            _ => panic!("test setup: expected Sparse"),
        }
    }

    #[test]
    fn test_apply_all_zeros() {
        let mut base = vec![10, 20, 30];
        let delta = InactivityDiff::AllZeros(5);

        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("test setup: serialize");
        let archived = rkyv::access::<ArchivedInactivityDiff, rkyv::rancor::Error>(&bytes)
            .expect("test setup: failed to access archived delta");

        apply_inactivity(&mut base, archived).expect("test setup: apply");

        assert_eq!(base, vec![0; 5]);
    }

    #[test]
    fn test_apply_sparse_roundtrip() {
        let base = vec![10, 20, 30, 40];
        let target = vec![10, 25, 30, 50, 60];

        let delta = diff_inactivity(&base, &target);

        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("test setup: serialize");
        let archived = rkyv::access::<ArchivedInactivityDiff, rkyv::rancor::Error>(&bytes)
            .expect("test setup: failed to access archived delta");

        let mut reconstructed = base;
        apply_inactivity(&mut reconstructed, archived).expect("test setup: apply");

        assert_eq!(reconstructed, target);
    }

    #[test]
    fn test_apply_sparse_mismatched_lengths() {
        let delta = InactivityDiff::Sparse {
            indices: vec![0u32],
            new_values: vec![],
            extensions: vec![],
        };

        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("test setup: serialize");
        let archived = rkyv::access::<ArchivedInactivityDiff, rkyv::rancor::Error>(&bytes)
            .expect("test setup: failed to access archived delta");

        let mut base = vec![0u64; 5];
        let result = apply_inactivity(&mut base, archived);

        assert!(result.is_err());
        let err_str = format!("{}", result.expect_err("test setup"));
        assert!(err_str.contains("indices but 0 replacement values"));
    }

    #[test]
    fn test_apply_sparse_index_out_of_bounds() {
        let delta = InactivityDiff::Sparse {
            indices: vec![10u32],
            new_values: vec![99u64],
            extensions: vec![],
        };

        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("test setup: serialize");
        let archived = rkyv::access::<ArchivedInactivityDiff, rkyv::rancor::Error>(&bytes)
            .expect("test setup: failed to access archived delta");

        let mut base = vec![0u64; 5];
        let result = apply_inactivity(&mut base, archived);

        assert!(result.is_err());
        let err_str = format!("{}", result.expect_err("test setup"));
        assert!(err_str.contains("index 10 is outside base vector of length 5"));
    }
}