spatialrust_web/
range.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use serde::{Deserialize, Serialize};
4
5use crate::{WebError, WebResult};
6
7/// Half-open remote byte range.
8#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
9pub struct ByteRange {
10    start: u64,
11    end_exclusive: u64,
12}
13
14#[derive(Deserialize)]
15#[serde(deny_unknown_fields)]
16struct ByteRangeInput {
17    start: u64,
18    end_exclusive: u64,
19}
20
21impl<'de> Deserialize<'de> for ByteRange {
22    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
23    where
24        D: serde::Deserializer<'de>,
25    {
26        let input = ByteRangeInput::deserialize(deserializer)?;
27        Self::try_new(input.start, input.end_exclusive).map_err(serde::de::Error::custom)
28    }
29}
30
31impl ByteRange {
32    /// Creates a non-empty range.
33    pub fn try_new(start: u64, end_exclusive: u64) -> WebResult<Self> {
34        if end_exclusive <= start {
35            return Err(WebError::Range("byte range must satisfy start < end_exclusive".into()));
36        }
37        Ok(Self { start, end_exclusive })
38    }
39
40    /// Inclusive start offset.
41    #[must_use]
42    pub const fn start(self) -> u64 {
43        self.start
44    }
45
46    /// Exclusive end offset.
47    #[must_use]
48    pub const fn end_exclusive(self) -> u64 {
49        self.end_exclusive
50    }
51
52    /// Range length.
53    #[must_use]
54    pub const fn len(self) -> u64 {
55        self.end_exclusive - self.start
56    }
57
58    /// A validated range is never empty.
59    #[must_use]
60    pub const fn is_empty(self) -> bool {
61        self.start == self.end_exclusive
62    }
63
64    /// HTTP `Range` header value.
65    #[must_use]
66    pub fn http_header(self) -> String {
67        format!("bytes={}-{}", self.start, self.end_exclusive - 1)
68    }
69}
70
71/// Hard limits for one remote planning/cache session.
72#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
73#[serde(deny_unknown_fields)]
74pub struct RangeBudget {
75    /// Maximum cache misses emitted by one plan.
76    pub max_requests_per_plan: usize,
77    /// Maximum aggregate bytes emitted by one plan.
78    pub max_requested_bytes_per_plan: u64,
79    /// Maximum one range length.
80    pub max_single_range_bytes: u64,
81    /// Maximum cached response bytes.
82    pub max_cache_bytes: u64,
83}
84
85impl RangeBudget {
86    /// Validates positive limits and compatible range/cache sizes.
87    pub fn validate(self) -> WebResult<()> {
88        if self.max_requests_per_plan == 0
89            || self.max_requested_bytes_per_plan == 0
90            || self.max_single_range_bytes == 0
91            || self.max_cache_bytes == 0
92            || self.max_single_range_bytes > self.max_requested_bytes_per_plan
93        {
94            return Err(WebError::Range(
95                "range limits must be positive and single-range <= per-plan bytes".into(),
96            ));
97        }
98        Ok(())
99    }
100}
101
102/// Deterministic cache-hit/fetch/denial decision.
103#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
104#[serde(deny_unknown_fields)]
105pub struct RangePlan {
106    /// Exact cached ranges.
107    pub cached: Vec<ByteRange>,
108    /// Misses admitted for fetch.
109    pub fetch: Vec<ByteRange>,
110    /// Requests denied by cancellation or hard limits.
111    pub denied: Vec<ByteRange>,
112    /// Exact admitted fetch bytes.
113    pub requested_bytes: u64,
114    /// Monotonic plan generation.
115    pub generation: u64,
116}
117
118/// Result of admitting one fetched response to the cache.
119#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
120#[serde(deny_unknown_fields)]
121pub struct RangeAdmissionReceipt {
122    /// Admitted range.
123    pub range: ByteRange,
124    /// Exact response bytes copied into the cache.
125    pub response_bytes: u64,
126    /// LRU ranges evicted before admission.
127    pub evicted: Vec<ByteRange>,
128    /// Cache bytes after admission.
129    pub cached_bytes: u64,
130}
131
132#[derive(Clone, Debug)]
133struct CacheEntry {
134    bytes: Vec<u8>,
135    last_used: u64,
136}
137
138/// Exact-range response cache with deterministic LRU eviction.
139#[derive(Clone, Debug)]
140pub struct RangeCache {
141    budget: RangeBudget,
142    entries: BTreeMap<ByteRange, CacheEntry>,
143    cached_bytes: u64,
144    tick: u64,
145}
146
147impl RangeCache {
148    /// Creates an empty cache.
149    pub fn try_new(budget: RangeBudget) -> WebResult<Self> {
150        budget.validate()?;
151        Ok(Self { budget, entries: BTreeMap::new(), cached_bytes: 0, tick: 0 })
152    }
153
154    /// Returns exact cached bytes and updates recency.
155    pub fn get(&mut self, range: ByteRange) -> Option<&[u8]> {
156        self.tick = self.tick.saturating_add(1);
157        let entry = self.entries.get_mut(&range)?;
158        entry.last_used = self.tick;
159        Some(&entry.bytes)
160    }
161
162    /// Whether an exact range is cached, without changing recency.
163    #[must_use]
164    pub fn contains(&self, range: ByteRange) -> bool {
165        self.entries.contains_key(&range)
166    }
167
168    /// Current cached bytes.
169    #[must_use]
170    pub const fn cached_bytes(&self) -> u64 {
171        self.cached_bytes
172    }
173
174    /// Admits an exact-length response, evicting deterministic LRU entries.
175    ///
176    /// Failure leaves the cache unchanged.
177    pub fn admit(
178        &mut self,
179        range: ByteRange,
180        response: Vec<u8>,
181    ) -> WebResult<RangeAdmissionReceipt> {
182        let expected = range.len();
183        let actual = u64::try_from(response.len())
184            .map_err(|_| WebError::Range("response length exceeds u64".into()))?;
185        if actual != expected {
186            return Err(WebError::Range(format!(
187                "range response length {actual} does not match requested {expected}"
188            )));
189        }
190        if actual > self.budget.max_single_range_bytes || actual > self.budget.max_cache_bytes {
191            return Err(WebError::Range(
192                "range response cannot fit single-range/cache budget".into(),
193            ));
194        }
195        let existing = self.entries.get(&range).map_or(0, |entry| entry.bytes.len() as u64);
196        let mut next_bytes = self
197            .cached_bytes
198            .checked_sub(existing)
199            .and_then(|value| value.checked_add(actual))
200            .ok_or_else(|| WebError::Range("cache byte accounting overflow".into()))?;
201        let mut candidates: Vec<_> = self
202            .entries
203            .iter()
204            .filter(|(candidate, _)| **candidate != range)
205            .map(|(candidate, entry)| (*candidate, entry.last_used, entry.bytes.len() as u64))
206            .collect();
207        candidates.sort_by_key(|(candidate, last_used, _)| (*last_used, *candidate));
208        let mut evicted = Vec::new();
209        for (candidate, _, bytes) in candidates {
210            if next_bytes <= self.budget.max_cache_bytes {
211                break;
212            }
213            next_bytes -= bytes;
214            evicted.push(candidate);
215        }
216        if next_bytes > self.budget.max_cache_bytes {
217            return Err(WebError::Range("cache capacity unavailable".into()));
218        }
219        let next_tick = self
220            .tick
221            .checked_add(1)
222            .ok_or_else(|| WebError::Range("cache recency overflow".into()))?;
223        for candidate in &evicted {
224            self.entries.remove(candidate);
225        }
226        self.tick = next_tick;
227        self.entries.insert(range, CacheEntry { bytes: response, last_used: self.tick });
228        self.cached_bytes = next_bytes;
229        Ok(RangeAdmissionReceipt {
230            range,
231            response_bytes: actual,
232            evicted,
233            cached_bytes: next_bytes,
234        })
235    }
236}
237
238/// Stateful deterministic range planner.
239#[derive(Clone, Debug)]
240pub struct RangePlanner {
241    budget: RangeBudget,
242    generation: u64,
243}
244
245impl RangePlanner {
246    /// Creates a planner.
247    pub fn try_new(budget: RangeBudget) -> WebResult<Self> {
248        budget.validate()?;
249        Ok(Self { budget, generation: 0 })
250    }
251
252    /// Deduplicates/sorts ranges and emits bounded cache misses.
253    pub fn plan(
254        &mut self,
255        ranges: impl IntoIterator<Item = ByteRange>,
256        cache: &RangeCache,
257        cancelled: bool,
258    ) -> WebResult<RangePlan> {
259        self.generation = self
260            .generation
261            .checked_add(1)
262            .ok_or_else(|| WebError::Range("range plan generation overflow".into()))?;
263        let ranges: BTreeSet<_> = ranges.into_iter().collect();
264        let mut plan = RangePlan { generation: self.generation, ..RangePlan::default() };
265        for range in ranges {
266            if range.is_empty() || range.len() > self.budget.max_single_range_bytes {
267                plan.denied.push(range);
268                continue;
269            }
270            if cache.contains(range) {
271                plan.cached.push(range);
272                continue;
273            }
274            let next_bytes = plan.requested_bytes.checked_add(range.len());
275            if cancelled
276                || plan.fetch.len() >= self.budget.max_requests_per_plan
277                || next_bytes.map_or(true, |bytes| bytes > self.budget.max_requested_bytes_per_plan)
278            {
279                plan.denied.push(range);
280                continue;
281            }
282            plan.requested_bytes = next_bytes.expect("checked above");
283            plan.fetch.push(range);
284        }
285        Ok(plan)
286    }
287}
288
289#[cfg(test)]
290mod tests {
291    use super::{ByteRange, RangeBudget, RangeCache, RangePlanner};
292
293    fn budget() -> RangeBudget {
294        RangeBudget {
295            max_requests_per_plan: 2,
296            max_requested_bytes_per_plan: 8,
297            max_single_range_bytes: 4,
298            max_cache_bytes: 8,
299        }
300    }
301
302    #[test]
303    fn plan_deduplicates_orders_hits_and_denies_before_fetch() {
304        let a = ByteRange::try_new(0, 4).unwrap();
305        let b = ByteRange::try_new(4, 8).unwrap();
306        let c = ByteRange::try_new(8, 12).unwrap();
307        let mut cache = RangeCache::try_new(budget()).unwrap();
308        cache.admit(a, vec![1; 4]).unwrap();
309        let mut planner = RangePlanner::try_new(budget()).unwrap();
310        let plan = planner.plan([c, b, a, b], &cache, false).unwrap();
311        assert_eq!(plan.cached, vec![a]);
312        assert_eq!(plan.fetch, vec![b, c]);
313        assert_eq!(plan.requested_bytes, 8);
314
315        let cancelled = planner.plan([b], &cache, true).unwrap();
316        assert!(cancelled.fetch.is_empty());
317        assert_eq!(cancelled.denied, vec![b]);
318    }
319
320    #[test]
321    fn range_json_rejects_empty_reversed_and_unknown_fields() {
322        assert!(serde_json::from_str::<ByteRange>(r#"{"start":4,"end_exclusive":4}"#).is_err());
323        assert!(serde_json::from_str::<ByteRange>(r#"{"start":8,"end_exclusive":4}"#).is_err());
324        assert!(serde_json::from_str::<ByteRange>(
325            r#"{"start":0,"end_exclusive":4,"unexpected":true}"#
326        )
327        .is_err());
328    }
329
330    #[test]
331    fn cache_checks_exact_length_and_evicts_lru_deterministically() {
332        let a = ByteRange::try_new(0, 4).unwrap();
333        let b = ByteRange::try_new(4, 8).unwrap();
334        let c = ByteRange::try_new(8, 12).unwrap();
335        let mut cache = RangeCache::try_new(budget()).unwrap();
336        cache.admit(a, vec![1; 4]).unwrap();
337        cache.admit(b, vec![2; 4]).unwrap();
338        cache.get(a).unwrap();
339        let receipt = cache.admit(c, vec![3; 4]).unwrap();
340        assert_eq!(receipt.evicted, vec![b]);
341        assert!(cache.contains(a));
342        assert!(cache.contains(c));
343        assert_eq!(cache.cached_bytes(), 8);
344
345        let before = cache.cached_bytes();
346        assert!(cache.admit(ByteRange::try_new(12, 16).unwrap(), vec![0; 3]).is_err());
347        assert_eq!(cache.cached_bytes(), before);
348    }
349}
spatialrust_web/range.rs

spatialrust_web/
range.rs
