eth-state-diff 0.2.3

//! Delta encoding for Phase 0 pending attestation lists.
//!
//! Phase 0 maintains two attestation lists with different update semantics:
//!
//! - `current_epoch_attestations` grows by appending new attestations during an
//!   epoch.
//! - `previous_epoch_attestations` is replaced when the epoch transitions.
//!
//! This module provides a single diff function that selects the most compact
//! supported representation for both cases. If the target list starts with the
//! exact byte sequence of the base list, only the appended bytes are stored.
//! Otherwise, the complete target list is stored as a full replacement.
//!
//! Both representations use [`AttestationsDiff`] and can be applied with
//! [`apply_attestations`] without deserializing individual attestations.

use crate::types::{ArchivedAttestationsDiff, AttestationsDiff};

/// Computes a compact delta between two serialized SSZ attestation lists.
///
/// The function automatically selects between the supported delta
/// representations:
///
/// - If the lists are identical, [`AttestationsDiff::Unchanged`] is returned.
/// - If the target list starts with the exact byte sequence of the base list,
///   only the trailing bytes are stored in [`AttestationsDiff::Append`].
/// - Otherwise, the complete target list is stored in
///   [`AttestationsDiff::FullReplacement`].
///
/// This covers both append-only updates, such as growth of
/// `current_epoch_attestations`, and epoch-boundary replacement of
/// `previous_epoch_attestations`.
///
/// An empty base list is naturally represented as an append of the complete
/// target list.
///
/// # Arguments
///
/// * `base_ssz` - Serialized SSZ representation of the base attestation list.
/// * `target_ssz` - Serialized SSZ representation of the target attestation list.
///
/// # Returns
///
/// A compact [`AttestationsDiff`] representing the transition from `base_ssz`
/// to `target_ssz`.
///
/// # Complexity
///
/// The prefix comparison takes O(min(n, m)) time, where *n* and *m* are the
/// lengths of `base_ssz` and `target_ssz`, respectively. Additional space is
/// proportional to the selected delta payload.
///
/// # Example
///
/// ```
/// # use eth_state_diff::attestations::diff_attestations;
/// # use eth_state_diff::types::AttestationsDiff;
///
/// let base = b"AAAA";
///
/// // Append case.
/// let target = b"AAAABBBB";
/// assert_eq!(
///     diff_attestations(base, target),
///     AttestationsDiff::Append(b"BBBB".to_vec())
/// );
///
/// // Replacement case.
/// let target = b"CCCC";
/// assert_eq!(
///     diff_attestations(base, target),
///     AttestationsDiff::FullReplacement(b"CCCC".to_vec())
/// );
/// ```
pub fn diff_attestations(base_ssz: &[u8], target_ssz: &[u8]) -> AttestationsDiff {
    if base_ssz == target_ssz {
        return AttestationsDiff::Unchanged;
    }

    if target_ssz.starts_with(base_ssz) {
        let appended = &target_ssz[base_ssz.len()..];
        AttestationsDiff::Append(appended.to_vec())
    } else {
        AttestationsDiff::FullReplacement(target_ssz.to_vec())
    }
}

/// Applies an attestation delta to a serialized SSZ list in place.
///
/// [`AttestationsDiff::Unchanged`] leaves the base buffer untouched.
///
/// [`AttestationsDiff::Append`] appends the serialized bytes stored in the
/// delta to the existing buffer.
///
/// [`AttestationsDiff::FullReplacement`] clears the existing buffer and
/// replaces it with the serialized target bytes.
///
/// # Complexity
///
/// - [`AttestationsDiff::Unchanged`][]: O(1).
/// - [`AttestationsDiff::Append`]: O(k), where *k* is the number of appended
///   bytes.
/// - [`AttestationsDiff::FullReplacement`]: O(n), where *n* is the size of the
///   replacement list.
///
/// # Example
///
/// ```
/// # use eth_state_diff::attestations::{apply_attestations, diff_attestations};
/// # use eth_state_diff::types::AttestationsDiff;
///
/// let mut base = b"AAAA".to_vec();
/// let delta = diff_attestations(&base, b"AAAABBBB");
///
/// match delta {
///     AttestationsDiff::Unchanged => {}
///     AttestationsDiff::Append(bytes) => base.extend_from_slice(&bytes),
///     AttestationsDiff::FullReplacement(bytes) => {
///         base.clear();
///         base.extend_from_slice(&bytes);
///     }
/// }
///
/// assert_eq!(base, b"AAAABBBB");
/// ```
pub fn apply_attestations(base: &mut Vec<u8>, delta: &ArchivedAttestationsDiff) {
    match delta {
        ArchivedAttestationsDiff::Unchanged => {}
        ArchivedAttestationsDiff::Append(bytes) => {
            base.extend_from_slice(bytes.as_slice());
        }
        ArchivedAttestationsDiff::FullReplacement(bytes) => {
            base.clear();
            base.extend_from_slice(bytes.as_slice());
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::{ArchivedAttestationsDiff, AttestationsDiff};
    use rkyv::Archive;

    fn archive(diff: &AttestationsDiff) -> rkyv::util::AlignedVec {
        rkyv::to_bytes::<rkyv::rancor::Error>(diff).expect("failed to archive diff")
    }

    fn archived(bytes: &[u8]) -> &ArchivedAttestationsDiff {
        rkyv::access::<ArchivedAttestationsDiff, rkyv::rancor::Error>(bytes)
            .expect("bytes are a valid rkyv payload generated by `archive`")
    }

    #[test]
    fn diff_identical_lists_is_unchanged() {
        assert_eq!(
            diff_attestations(b"AAAA", b"AAAA"),
            AttestationsDiff::Unchanged
        );
    }

    #[test]
    fn diff_target_extends_base_is_append() {
        assert_eq!(
            diff_attestations(b"AAAA", b"AAAABBBB"),
            AttestationsDiff::Append(b"BBBB".to_vec()),
        );
    }

    #[test]
    fn diff_target_diverges_is_full_replacement() {
        assert_eq!(
            diff_attestations(b"AAAA", b"CCCC"),
            AttestationsDiff::FullReplacement(b"CCCC".to_vec()),
        );
    }

    #[test]
    fn diff_target_diverges_mid_item_is_full_replacement() {
        let base = b"AAAA-BBBB-CCCC-DDDD";
        let target = b"AAAA-BBBB-XXXX-DDDD";
        assert_eq!(
            diff_attestations(base, target),
            AttestationsDiff::FullReplacement(target.to_vec()),
        );
    }

    #[test]
    fn diff_empty_base_to_nonempty_is_append() {
        assert_eq!(
            diff_attestations(b"", b"AAAABBBB"),
            AttestationsDiff::Append(b"AAAABBBB".to_vec()),
        );
    }

    #[test]
    fn diff_both_empty_is_unchanged() {
        assert_eq!(diff_attestations(b"", b""), AttestationsDiff::Unchanged);
    }

    #[test]
    fn diff_nonempty_base_to_empty_is_replacement_with_empty_payload() {
        assert_eq!(
            diff_attestations(b"AAAA", b""),
            AttestationsDiff::FullReplacement(Vec::new()),
        );
    }

    #[test]
    fn apply_unchanged_leaves_buffer_untouched() {
        let buf = archive(&AttestationsDiff::Unchanged);
        let mut base = b"AAAA".to_vec();
        apply_attestations(&mut base, archived(&buf));
        assert_eq!(base, b"AAAA");
    }

    #[test]
    fn apply_append_extends_buffer_in_place() {
        let buf = archive(&AttestationsDiff::Append(b"BBBB".to_vec()));
        let mut base = b"AAAA".to_vec();
        apply_attestations(&mut base, archived(&buf));
        assert_eq!(base, b"AAAABBBB");
    }

    #[test]
    fn apply_full_replacement_clears_then_writes() {
        let buf = archive(&AttestationsDiff::FullReplacement(b"CCCC".to_vec()));
        let mut base = b"AAAA".to_vec();
        apply_attestations(&mut base, archived(&buf));
        assert_eq!(base, b"CCCC");

        let buf = archive(&AttestationsDiff::FullReplacement(Vec::new()));
        apply_attestations(&mut base, archived(&buf));
        assert!(base.is_empty());
    }

    fn round_trip(base: &[u8], target: &[u8]) {
        let diff = diff_attestations(base, target);
        let buf = archive(&diff);
        let mut current = base.to_vec();
        apply_attestations(&mut current, archived(&buf));
        assert_eq!(
            current, target,
            "round-trip failed for base={base:?} target={target:?}"
        );
    }

    #[test]
    fn round_trip_covers_all_branches() {
        round_trip(b"AAAA", b"AAAA");
        round_trip(b"AAAA", b"AAAABBBB");
        round_trip(b"AAAA", b"CCCC");
        round_trip(b"", b"AAAABBBB");
        round_trip(b"", b"");
        round_trip(b"AAAA", b"");
        round_trip(b"AAAA-BBBB-CCCC-DDDD", b"AAAA-BBBB-XXXX-DDDD");
    }

    #[test]
    fn round_trip_epoch_lifecycle_appends_then_replaces() {
        let mut state: Vec<u8> = Vec::new();
        let mut expected = Vec::new();

        for chunk in [b"att1".as_slice(), b"att2", b"att3"] {
            expected.extend_from_slice(chunk);
            let buf = archive(&diff_attestations(&state, &expected));
            apply_attestations(&mut state, archived(&buf));
            assert_eq!(state, expected);
        }

        // Epoch boundary: replace previous_epoch_attestations wholesale.
        let new_epoch = b"prev1-prev2";
        let diff = diff_attestations(&state, new_epoch);
        assert!(
            matches!(diff, AttestationsDiff::FullReplacement(_)),
            "epoch transition must be a full replacement, got {diff:?}"
        );
        let buf = archive(&diff);
        apply_attestations(&mut state, archived(&buf));
        assert_eq!(state, new_epoch);

        // New epoch appends again.
        let mut expected = new_epoch.to_vec();
        expected.extend_from_slice(b"-att4");
        let diff = diff_attestations(&state, &expected);
        assert!(
            matches!(diff, AttestationsDiff::Append(_)),
            "intra-epoch update must be an append, got {diff:?}"
        );
        let buf = archive(&diff);
        apply_attestations(&mut state, archived(&buf));
        assert_eq!(state, expected);
    }

    #[test]
    fn round_trip_large_payloads() {
        let one_att = b"AAAAAAAA-BBBBBBBB-CCCCCCCC-DDDDDDDD-EEEEEEEE";
        let mut base = Vec::new();
        for _ in 0..32 {
            base.extend_from_slice(one_att);
        }

        let mut target = base.clone();
        target.extend_from_slice(one_att);
        target.extend_from_slice(one_att);

        let diff = diff_attestations(&base, &target);
        assert!(matches!(diff, AttestationsDiff::Append(_)));
        let buf = archive(&diff);
        let mut current = base.clone();
        apply_attestations(&mut current, archived(&buf));
        assert_eq!(current, target);

        // Diverge at first byte -> full replacement.
        let mut divergent = target.clone();
        *divergent.get_mut(0).expect("target vector is non-empty") ^= 0xFF;
        let diff = diff_attestations(&current, &divergent);
        assert!(matches!(diff, AttestationsDiff::FullReplacement(_)));
        let buf = archive(&diff);
        apply_attestations(&mut current, archived(&buf));
        assert_eq!(current, divergent);
    }

    #[test]
    fn archived_alias_matches_attestations_diff() {
        fn _assert_archived<T: Archive<Archived = ArchivedAttestationsDiff>>() {}
        _assert_archived::<AttestationsDiff>();
    }
}