cellos-supervisor 0.5.1

//! HPACK dynamic table (RFC 7541 §2.3.2 + §4.1 + §4.2 + §4.4).
//!
//! Per-connection state evolved by literal-with-incremental-indexing
//! representations. Newest entry is at the front of the deque (lowest
//! relative dynamic-table index).
//!
//! ## Defensive bound on `max_size`
//!
//! RFC 7540 §6.5.2 default `SETTINGS_HEADER_TABLE_SIZE` is 4096 octets and
//! the spec allows arbitrary peer-driven updates (no upper bound). Accepting
//! unbounded sizes is a memory-amplification vector — an adversarial workload
//! could send a `SETTINGS_HEADER_TABLE_SIZE = u32::MAX` followed by a stream
//! of large literal-with-incremental-indexing entries to wedge the proxy.
//!
//! Phase 3g caps `max_size` at [`MAX_TABLE_SIZE`] (65 536 octets — 16× the
//! default). Updates above this surface as
//! [`H2ParseError::HpackTableSizeOversized`].

use std::collections::VecDeque;

use super::super::error::H2ParseError;
use super::static_table::STATIC_TABLE_MAX;

/// Defensive ceiling on `SETTINGS_HEADER_TABLE_SIZE`. RFC 7540 imposes none;
/// 64 KiB is a sane upper bound for an authority-extracting proxy and aligns
/// with the `MAX_HEADER_BLOCK_SIZE` used by the CONTINUATION reassembler.
pub const MAX_TABLE_SIZE: usize = 64 * 1024;

/// RFC 7541 §4.1 — every entry's accounting size includes a 32-octet
/// overhead beyond `name + value`.
pub const ENTRY_OVERHEAD: usize = 32;

/// Bounded LRU-evicting dynamic table per RFC 7541.
#[derive(Debug)]
pub struct DynamicTable {
    /// Newest entry at index 0 per RFC 7541 §2.3.3 (i.e. at the **front**
    /// of the deque). The first dynamic-table slot is **HPACK absolute
    /// index 62** (immediately above the 61-row static table).
    entries: VecDeque<(String, String)>,
    /// Sum of `entry_size(name, value)` across all entries.
    size_octets: usize,
    /// Soft limit driven by `SETTINGS_HEADER_TABLE_SIZE`. Defaults to
    /// 4096 per RFC 7540 §6.5.2.
    max_size: usize,
}

impl DynamicTable {
    /// Create a new dynamic table with `max_size` octets of capacity. If
    /// `max_size` exceeds [`MAX_TABLE_SIZE`] the constructor returns
    /// [`H2ParseError::HpackTableSizeOversized`].
    pub fn new(max_size: usize) -> Result<Self, H2ParseError> {
        if max_size > MAX_TABLE_SIZE {
            return Err(H2ParseError::HpackTableSizeOversized {
                requested: max_size,
                max: MAX_TABLE_SIZE,
            });
        }
        Ok(Self {
            entries: VecDeque::new(),
            size_octets: 0,
            max_size,
        })
    }

    /// RFC 7541 §4.1 entry size: name + value + 32 octets of overhead.
    pub fn entry_size(name: &str, value: &str) -> usize {
        name.len() + value.len() + ENTRY_OVERHEAD
    }

    /// Look up by HPACK *absolute* index (the same index space the
    /// `Indexed Header Field` representation carries). Indices 1..=61 hit
    /// the static table; indices ≥ 62 hit the dynamic table starting at
    /// `entries[0]` (newest).
    pub fn lookup(&self, idx: u64) -> Option<(&str, &str)> {
        if idx == 0 {
            return None;
        }
        if idx <= STATIC_TABLE_MAX {
            return super::static_table::lookup_static(idx).map(|(n, v)| (*n, *v));
        }
        // Dynamic side: 62 → entries[0], 63 → entries[1], ...
        let dyn_idx = (idx - STATIC_TABLE_MAX - 1) as usize;
        self.entries
            .get(dyn_idx)
            .map(|(n, v)| (n.as_str(), v.as_str()))
    }

    /// RFC 7541 §4.4: insert at the front and evict from the back until
    /// `size_octets <= max_size`. If a single entry's size exceeds
    /// `max_size` the table is cleared and the entry is NOT added (per the
    /// final paragraph of §4.4).
    pub fn insert(&mut self, name: String, value: String) {
        let new_size = Self::entry_size(&name, &value);
        if new_size > self.max_size {
            // Per §4.4: an attempt to add an entry larger than the maximum
            // size causes the table to be emptied of all existing entries
            // and results in an empty table.
            self.entries.clear();
            self.size_octets = 0;
            return;
        }
        // Evict from the back until we have room.
        while self.size_octets + new_size > self.max_size {
            if let Some((n, v)) = self.entries.pop_back() {
                self.size_octets = self.size_octets.saturating_sub(Self::entry_size(&n, &v));
            } else {
                break;
            }
        }
        self.size_octets += new_size;
        self.entries.push_front((name, value));
    }

    /// RFC 7541 §4.3: SETTINGS_HEADER_TABLE_SIZE update from the encoder.
    /// Evicts from the back until `size_octets <= new_max`. Rejects any
    /// `new_max > MAX_TABLE_SIZE` defensively.
    pub fn update_max_size(&mut self, new_max: usize) -> Result<(), H2ParseError> {
        if new_max > MAX_TABLE_SIZE {
            return Err(H2ParseError::HpackTableSizeOversized {
                requested: new_max,
                max: MAX_TABLE_SIZE,
            });
        }
        self.max_size = new_max;
        while self.size_octets > new_max {
            if let Some((n, v)) = self.entries.pop_back() {
                self.size_octets = self.size_octets.saturating_sub(Self::entry_size(&n, &v));
            } else {
                break;
            }
        }
        Ok(())
    }

    pub fn entry_count(&self) -> usize {
        self.entries.len()
    }

    pub fn size_octets(&self) -> usize {
        self.size_octets
    }

    #[cfg(test)]
    pub fn max_size(&self) -> usize {
        self.max_size
    }
}

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

    #[test]
    fn static_index_1_returns_authority_empty() {
        let t = DynamicTable::new(4096).unwrap();
        let (name, value) = t.lookup(1).unwrap();
        assert_eq!(name, ":authority");
        assert_eq!(value, "");
    }

    #[test]
    fn dynamic_index_62_returns_first_inserted_entry() {
        let mut t = DynamicTable::new(4096).unwrap();
        t.insert(":authority".into(), "api.example.com".into());
        let (name, value) = t.lookup(62).unwrap();
        assert_eq!(name, ":authority");
        assert_eq!(value, "api.example.com");
        assert_eq!(t.entry_count(), 1);
        assert_eq!(
            t.size_octets(),
            ":authority".len() + "api.example.com".len() + 32
        );
    }

    #[test]
    fn insert_evicts_oldest_when_oversized() {
        // max = enough for exactly one ~50-octet entry.
        let mut t = DynamicTable::new(60).unwrap();
        t.insert("a".into(), "x".into()); // 1 + 1 + 32 = 34
        t.insert("b".into(), "y".into()); // would push total to 68 → evict 'a'
        assert_eq!(t.entry_count(), 1);
        let (name, value) = t.lookup(62).unwrap();
        assert_eq!(name, "b");
        assert_eq!(value, "y");
    }

    #[test]
    fn update_max_size_zero_clears_table() {
        let mut t = DynamicTable::new(4096).unwrap();
        t.insert("a".into(), "b".into());
        assert_eq!(t.entry_count(), 1);
        t.update_max_size(0).unwrap();
        assert_eq!(t.entry_count(), 0);
        assert_eq!(t.size_octets(), 0);
        assert_eq!(t.max_size(), 0);
    }

    #[test]
    fn entry_size_includes_32_octet_overhead() {
        assert_eq!(DynamicTable::entry_size("a", "b"), 1 + 1 + 32);
        assert_eq!(DynamicTable::entry_size("", ""), 32);
        assert_eq!(
            DynamicTable::entry_size(":authority", "api.example.com"),
            ":authority".len() + "api.example.com".len() + 32
        );
    }

    #[test]
    fn oversized_max_size_rejected() {
        let err = DynamicTable::new(MAX_TABLE_SIZE + 1).unwrap_err();
        assert!(matches!(err, H2ParseError::HpackTableSizeOversized { .. }));
        let mut t = DynamicTable::new(4096).unwrap();
        let err = t.update_max_size(MAX_TABLE_SIZE + 1).unwrap_err();
        assert!(matches!(err, H2ParseError::HpackTableSizeOversized { .. }));
    }

    #[test]
    fn lookup_out_of_range_returns_none() {
        let t = DynamicTable::new(4096).unwrap();
        assert!(t.lookup(0).is_none());
        assert!(t.lookup(62).is_none()); // dynamic table empty
        assert!(t.lookup(u64::MAX).is_none());
    }

    #[test]
    fn insert_oversized_single_entry_clears_table_per_rfc_7541_4_4() {
        let mut t = DynamicTable::new(60).unwrap();
        t.insert("a".into(), "b".into());
        assert_eq!(t.entry_count(), 1);
        // Single entry whose size > 60 must clear the table without adding.
        let big_value: String = std::iter::repeat_n('x', 100).collect();
        t.insert("name".into(), big_value);
        assert_eq!(t.entry_count(), 0);
        assert_eq!(t.size_octets(), 0);
    }

    #[test]
    fn lookup_static_pseudo_headers_intact() {
        let t = DynamicTable::new(4096).unwrap();
        // Spot-check a few static entries beyond :authority.
        assert_eq!(t.lookup(2).unwrap(), (":method", "GET"));
        assert_eq!(t.lookup(7).unwrap(), (":scheme", "https"));
        assert_eq!(t.lookup(38).unwrap(), ("host", ""));
    }
}