Skip to main content

shaul_core/
range.rs

1use serde::{Deserialize, Serialize};
2
3use crate::error::{Error, Result};
4
5/// A byte range with an exclusive end. Used for HTTP segments and resume
6/// manifests.
7#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
8pub struct ByteRange {
9    pub start: u64,
10    /// Exclusive.
11    pub end: u64,
12}
13
14impl ByteRange {
15    pub fn new(start: u64, end: u64) -> Result<Self> {
16        if start >= end {
17            return Err(Error::Other(format!("invalid byte range {start}..{end}")));
18        }
19        Ok(Self { start, end })
20    }
21
22    pub fn len(&self) -> u64 {
23        self.end - self.start
24    }
25
26    pub fn is_empty(&self) -> bool {
27        self.start >= self.end
28    }
29
30    pub fn contains(&self, other: &ByteRange) -> bool {
31        self.start <= other.start && other.end <= self.end
32    }
33}
34
35/// Sort and coalesce overlapping or adjacent ranges.
36pub fn merge_ranges(mut ranges: Vec<ByteRange>) -> Vec<ByteRange> {
37    ranges.retain(|range| !range.is_empty());
38    ranges.sort_by_key(|range| range.start);
39    let mut merged: Vec<ByteRange> = Vec::with_capacity(ranges.len());
40    for range in ranges {
41        match merged.last_mut() {
42            Some(last) if range.start <= last.end => {
43                if range.end > last.end {
44                    last.end = range.end;
45                }
46            }
47            _ => merged.push(range),
48        }
49    }
50    merged
51}
52
53/// Complement of `completed` inside `0..total`.
54pub fn missing_ranges(total: u64, completed: &[ByteRange]) -> Vec<ByteRange> {
55    let completed = merge_ranges(completed.to_vec());
56    let mut missing = Vec::new();
57    let mut cursor = 0u64;
58    for range in completed {
59        if range.start > cursor
60            && let Ok(gap) = ByteRange::new(cursor, range.start.min(total))
61        {
62            missing.push(gap);
63        }
64        cursor = cursor.max(range.end);
65        if cursor >= total {
66            break;
67        }
68    }
69    if cursor < total
70        && let Ok(gap) = ByteRange::new(cursor, total)
71    {
72        missing.push(gap);
73    }
74    missing
75}
76
77pub fn completed_bytes(completed: &[ByteRange]) -> u64 {
78    merge_ranges(completed.to_vec())
79        .iter()
80        .map(ByteRange::len)
81        .sum()
82}
83
84/// Drop or clamp ranges that extend past the known file length.
85pub fn clamp_to_len(ranges: &[ByteRange], len: u64) -> Vec<ByteRange> {
86    ranges
87        .iter()
88        .filter_map(|range| {
89            if range.start >= len {
90                None
91            } else {
92                ByteRange::new(range.start, range.end.min(len)).ok()
93            }
94        })
95        .collect()
96}
97
98/// Split a range into chunks of at most `chunk_size` bytes.
99pub fn split_range(range: ByteRange, chunk_size: u64) -> Vec<ByteRange> {
100    let chunk_size = chunk_size.max(1);
101    let mut chunks = Vec::new();
102    let mut start = range.start;
103    while start < range.end {
104        let end = (start + chunk_size).min(range.end);
105        if let Ok(chunk) = ByteRange::new(start, end) {
106            chunks.push(chunk);
107        }
108        start = end;
109    }
110    chunks
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn merges_adjacent_and_overlapping() {
119        let merged = merge_ranges(vec![
120            ByteRange::new(0, 10).unwrap(),
121            ByteRange::new(10, 20).unwrap(),
122            ByteRange::new(15, 25).unwrap(),
123            ByteRange::new(40, 50).unwrap(),
124        ]);
125        assert_eq!(
126            merged,
127            vec![
128                ByteRange::new(0, 25).unwrap(),
129                ByteRange::new(40, 50).unwrap()
130            ]
131        );
132    }
133
134    #[test]
135    fn computes_missing_ranges() {
136        let missing = missing_ranges(
137            100,
138            &[
139                ByteRange::new(10, 20).unwrap(),
140                ByteRange::new(50, 60).unwrap(),
141            ],
142        );
143        assert_eq!(
144            missing,
145            vec![
146                ByteRange::new(0, 10).unwrap(),
147                ByteRange::new(20, 50).unwrap(),
148                ByteRange::new(60, 100).unwrap()
149            ]
150        );
151    }
152
153    #[test]
154    fn splits_ranges() {
155        let chunks = split_range(ByteRange::new(0, 10).unwrap(), 4);
156        assert_eq!(
157            chunks,
158            vec![
159                ByteRange::new(0, 4).unwrap(),
160                ByteRange::new(4, 8).unwrap(),
161                ByteRange::new(8, 10).unwrap()
162            ]
163        );
164    }
165}