eth_state_diff/
fifo_queue.rs

1//! Delta encoding for fixed-size SSZ FIFO queues.
2//!
3//! A queue transition is represented as the number of items consumed from the
4//! front of the queue together with the raw SSZ bytes of newly appended items.
5//!
6//! This encoding is suitable for append-only FIFO structures such as the
7//! Electra pending operation queues.
8
9use crate::types::{ArchivedFifoQueueDiff, FifoQueueDiff};
10
11/// Finds the first occurrence of an SSZ-encoded queue item within a byte slice.
12///
13/// Returns the byte offset of the first matching item, or `None` if no match is
14/// found.
15fn find_chunk(haystack: &[u8], needle: &[u8]) -> Option<usize> {
16    haystack
17        .windows(needle.len())
18        .position(|window| window == needle)
19}
20
21/// Computes the delta between two serialized FIFO queues.
22///
23/// The queues are expected to contain fixed-size SSZ items.
24///
25/// The resulting delta records:
26///
27/// - the number of items consumed from the front of the base queue; and
28/// - the SSZ bytes of items appended to the end of the queue.
29///
30/// If no overlap between the queues can be identified, the encoder assumes the
31/// base queue was entirely consumed.
32///
33/// # Algorithm
34///
35/// The encoder identifies the overlap by locating the first item in the target
36/// queue within the base queue. This assumes queue items are sufficiently
37/// unique that the first match represents the correct continuation of the FIFO
38/// sequence.
39pub fn diff_fifo_queue(base_ssz: &[u8], target_ssz: &[u8], item_ssz_size: usize) -> FifoQueueDiff {
40    if target_ssz.is_empty() {
41        return FifoQueueDiff {
42            consumed_count: base_ssz.len() as u32 / item_ssz_size as u32,
43            appended_items: Vec::new(),
44        };
45    }
46
47    // If target is larger than base, no items were consumed, it's pure append
48    if target_ssz.len() >= base_ssz.len() {
49        let appended = if base_ssz.is_empty() {
50            target_ssz.to_vec()
51        } else {
52            target_ssz[base_ssz.len()..].to_vec()
53        };
54        return FifoQueueDiff {
55            consumed_count: 0,
56            appended_items: appended,
57        };
58    }
59
60    // Target shrank. We need to find how many items were consumed.
61    // Take the SSZ bytes of the first item in the target queue
62    let target_head = &target_ssz[..item_ssz_size];
63
64    match find_chunk(base_ssz, target_head) {
65        Some(byte_offset) => {
66            let consumed_count = (byte_offset / item_ssz_size) as u32;
67            let remaining_base_items = (base_ssz.len() - byte_offset) as u32;
68            let target_item_count = (target_ssz.len() / item_ssz_size) as u32;
69
70            let new_item_count = target_item_count.saturating_sub(remaining_base_items);
71            let new_items_start = target_ssz.len() - (new_item_count as usize * item_ssz_size);
72
73            FifoQueueDiff {
74                consumed_count,
75                appended_items: target_ssz[new_items_start..].to_vec(),
76            }
77        }
78        None => FifoQueueDiff {
79            consumed_count: base_ssz.len() as u32 / item_ssz_size as u32,
80            appended_items: target_ssz.to_vec(),
81        },
82    }
83}
84
85/// Applies a FIFO queue delta in place.
86///
87/// The destination queue is updated by:
88///
89/// 1. Removing `consumed_count` items from the front.
90/// 2. Appending the recorded SSZ items to the end.
91///
92/// If `consumed_count` exceeds the current queue length, the destination queue
93/// is cleared before appending.
94///
95/// # Complexity
96///
97/// O(queue size + appended bytes)
98pub fn apply_fifo_queue(base: &mut Vec<u8>, delta: &ArchivedFifoQueueDiff, item_ssz_size: usize) {
99    let bytes_to_drain = delta.consumed_count.to_native() as usize * item_ssz_size;
100    if bytes_to_drain > base.len() {
101        base.clear();
102    } else {
103        base.drain(..bytes_to_drain);
104    }
105
106    if !delta.appended_items.is_empty() {
107        base.extend_from_slice(delta.appended_items.as_slice());
108    }
109}
eth_state_diff/fifo_queue.rs

eth_state_diff/
fifo_queue.rs
