fuchsia_repo/
range.rs

1// Copyright 2022 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use hyper::header::HeaderValue;
6
7/// Error returned if the range failed to parse.
8#[derive(Debug, thiserror::Error)]
9pub enum Error {
10    #[error("parse error")]
11    Parse,
12
13    #[error("overflow")]
14    Overflow,
15
16    #[error("multipart ranges are not supported")]
17    MultipartRangesAreUnsupported,
18
19    #[error("unknown values are not supported")]
20    UnknownValuesAreNotSupported,
21}
22
23/// [Range] denotes a range of requested bytes for a [Resource].
24///
25/// This mostly matches the semantics of the http Range header according to [RFC-7233], but we
26/// only support a single range request, rather than multiple requests.
27///
28/// [RFC-7233]: https://httpwg.org/specs/rfc7233.html#range.requests
29#[derive(Debug, Copy, Clone, PartialEq, Eq)]
30pub enum Range {
31    /// A range that requests the full range of bytes from a resource.
32    Full,
33
34    /// A range that requests a subset of bytes from a resource, `first_byte_pos <= x`.
35    From { first_byte_pos: u64 },
36
37    /// A range that requests a subset of bytes from a resource, `first_byte_pos <= x && x <=
38    /// last_byte_pos`.
39    Inclusive { first_byte_pos: u64, last_byte_pos: u64 },
40
41    /// A range that requests a subset of bytes from the end of the resource, or `total - len <= x`.
42    Suffix { len: u64 },
43}
44
45impl Range {
46    /// Parse an HTTP Range header according to [RFC-7233].
47    ///
48    /// [RFC-7233]: https://httpwg.org/specs/rfc7233.html#range.requests
49    pub fn from_http_range_header(header: &HeaderValue) -> Result<Self, Error> {
50        parse_range(header.as_ref())
51    }
52
53    pub fn to_http_request_header(&self) -> Option<HeaderValue> {
54        let value = match self {
55            Range::Full => {
56                return None;
57            }
58            Range::Inclusive { first_byte_pos, last_byte_pos } => {
59                format!("bytes={first_byte_pos}-{last_byte_pos}")
60            }
61            Range::From { first_byte_pos } => {
62                format!("bytes={first_byte_pos}-")
63            }
64            Range::Suffix { len } => {
65                format!("bytes=-{len}")
66            }
67        };
68
69        // The unwrap should be safe here since HeaderValue only fails if there are
70        // non-ascii characters in the string.
71        let header =
72            HeaderValue::from_str(&value).expect("header to only contain ASCII characters");
73
74        Some(header)
75    }
76}
77
78/// [ContentLength] denotes the size of a [Resource].
79///
80/// This matches the semantics of the http Content-Length header according to [RFC-7230].
81///
82/// [RFC-7230]: https://httpwg.org/specs/rfc7230.html#header.content-length
83#[derive(Copy, Clone, Debug, PartialEq, Eq)]
84pub struct ContentLength(u64);
85
86impl ContentLength {
87    pub fn new(content_len: u64) -> Self {
88        Self(content_len)
89    }
90
91    /// Parse an HTTP Content-Length header according to [RFC-7230].
92    ///
93    /// [RFC-7230]: https://httpwg.org/specs/rfc7230.html#header.content-length
94    pub fn from_http_content_length_header(header: &HeaderValue) -> Result<Self, Error> {
95        let content_len = parse_integer(header.as_ref())?;
96        Ok(ContentLength(content_len))
97    }
98
99    /// Return the content length as a [u64].
100    pub fn as_u64(&self) -> u64 {
101        self.0
102    }
103
104    pub fn contains_range(&self, range: Range) -> bool {
105        match range {
106            Range::Full => true,
107            Range::From { first_byte_pos } => first_byte_pos < self.0,
108            Range::Inclusive { first_byte_pos, last_byte_pos } => {
109                first_byte_pos <= last_byte_pos && first_byte_pos < self.0 && last_byte_pos < self.0
110            }
111            Range::Suffix { len } => len <= self.0,
112        }
113    }
114}
115
116/// [ContentRange] denotes the size of a [Resource].
117///
118/// This mostly matches the semantics of the http Content-Range header according to [RFC-7233], but
119/// we require that the complete length of the resource must be known.
120///
121/// [RFC-7233]: https://httpwg.org/specs/rfc7233.html#header.content-range
122#[derive(Copy, Clone, Debug, PartialEq, Eq)]
123pub enum ContentRange {
124    /// Denotes that the resource contains the full range of bytes.
125    Full { complete_len: u64 },
126
127    /// Denotes that the resource contains a partial range of bytes between `start >= x && x <= end`,
128    /// inclusive.
129    Inclusive { first_byte_pos: u64, last_byte_pos: u64, complete_len: u64 },
130}
131
132impl ContentRange {
133    /// Parse an HTTP Content-Length header according to [RFC-7230].
134    ///
135    /// [RFC-7230]: https://httpwg.org/specs/rfc7230.html#header.content-length
136    pub fn from_http_content_length_header(header: &HeaderValue) -> Result<Self, Error> {
137        Ok(ContentLength::from_http_content_length_header(header)?.into())
138    }
139
140    /// Parse an HTTP Content-Range header according to [RFC-7233].
141    ///
142    /// [RFC-7233]: https://httpwg.org/specs/rfc7233.html#header.content-range
143    pub fn from_http_content_range_header(header: &HeaderValue) -> Result<Self, Error> {
144        parse_content_range(header.as_ref())
145    }
146
147    /// Return the content length of the range, which may be smaller than the total length of the range.
148    pub fn content_len(&self) -> u64 {
149        match self {
150            ContentRange::Full { complete_len } => *complete_len,
151
152            ContentRange::Inclusive { first_byte_pos, last_byte_pos, .. } => {
153                if first_byte_pos > last_byte_pos {
154                    0
155                } else {
156                    // Partial is an inclusive range, so we need to add one to compute the total length.
157                    let end = last_byte_pos.saturating_add(1);
158                    end - first_byte_pos
159                }
160            }
161        }
162    }
163
164    /// Return the total length of the range.
165    pub fn total_len(&self) -> u64 {
166        match self {
167            ContentRange::Full { complete_len } | ContentRange::Inclusive { complete_len, .. } => {
168                *complete_len
169            }
170        }
171    }
172
173    pub fn to_http_content_range_header(&self) -> Option<HeaderValue> {
174        match self {
175            ContentRange::Full { .. } => None,
176            ContentRange::Inclusive { first_byte_pos, last_byte_pos, complete_len } => {
177                let value = format!("bytes {first_byte_pos}-{last_byte_pos}/{complete_len}");
178
179                // The unwrap should be safe here since HeaderValue only fails if there are
180                // non-ascii characters in the string.
181                let header = HeaderValue::from_str(&value)
182                    .expect("header to not contain illegal characters");
183
184                Some(header)
185            }
186        }
187    }
188}
189
190impl From<ContentLength> for ContentRange {
191    fn from(content_len: ContentLength) -> Self {
192        Self::Full { complete_len: content_len.0 }
193    }
194}
195
196/// Parse a Range header.
197///
198///     Range                 = byte-ranges-specifier / other-ranges-specifier
199///     byte-ranges-specifier = bytes-unit "=" byte-range-set
200///     bytes-unit            = "bytes"
201///     byte-range-set        = *( "," OWS ) ( byte-range-spec / suffix-byte-range-spec )
202///                             *( OWS "," [ OWS ( byte-range-spec / suffix-byte-range-spec ) ] )
203fn parse_range(s: &[u8]) -> Result<Range, Error> {
204    let s = s.strip_prefix(b"bytes=").ok_or(Error::Parse)?;
205
206    let byte_range_set = s
207        .split(|ch| *ch == b',')
208        .map(|s| {
209            let s = skip_whitespce(s);
210            parse_byte_range_spec(s)
211        })
212        .collect::<Result<Vec<_>, _>>()?;
213
214    // Error out if we did not parse at least one range spec.
215    let mut byte_range_set = byte_range_set.into_iter();
216    let byte_range_spec = byte_range_set.next().ok_or(Error::Parse)?;
217
218    // FIXME: we only support one range part at the moment.
219    if byte_range_set.next().is_some() {
220        Err(Error::MultipartRangesAreUnsupported)
221    } else {
222        Ok(byte_range_spec)
223    }
224}
225
226/// Parse whitespace.
227///
228///     OWS = *( SP / HTAB )
229fn skip_whitespce(s: &[u8]) -> &[u8] {
230    if let Some(pos) = s.iter().position(|ch| *ch != b' ' && *ch != b'\t') {
231        &s[pos..]
232    } else {
233        b""
234    }
235}
236
237/// Parse a byte range spec.
238///
239///     byte-range-spec        = first-byte-pos "-" [ last-byte-pos ]
240///     suffix-byte-range-spec = "-" suffix-length
241///     first-byte-pos         = 1*DIGIT
242///     last-byte-pos          = 1*DIGIT
243fn parse_byte_range_spec(s: &[u8]) -> Result<Range, Error> {
244    let (first_byte_pos, last_byte_pos) = split_once(s, b'-').ok_or(Error::Parse)?;
245
246    if first_byte_pos.is_empty() {
247        // If we don't have a first-byte-pos, then we're parsing a suffix-byte-range-spec.
248        let last_byte_pos = parse_integer(last_byte_pos)?;
249
250        Ok(Range::Suffix { len: last_byte_pos })
251    } else {
252        let first_byte_pos = parse_integer(first_byte_pos)?;
253        if let Some(last_byte_pos) = parse_optional_integer(last_byte_pos)? {
254            Ok(Range::Inclusive { first_byte_pos, last_byte_pos })
255        } else {
256            Ok(Range::From { first_byte_pos })
257        }
258    }
259}
260
261/// Parse a Content-Range header.
262///
263///     Content-Range       = byte-content-range
264///     byte-content-range  = bytes-unit SP ( byte-range-resp / unsatisfied-range )
265///     byte-range-resp     = byte-range "/" ( complete-length / "*" )
266///     byte-range          = first-byte-pos "-" last-byte-pos
267fn parse_content_range(s: &[u8]) -> Result<ContentRange, Error> {
268    let s = s.strip_prefix(b"bytes ").ok_or(Error::Parse)?;
269    let (byte_range, complete_len) = split_once(s, b'/').ok_or(Error::Parse)?;
270    let (first_byte_pos, last_byte_pos) = split_once(byte_range, b'-').ok_or(Error::Parse)?;
271
272    let first_byte_pos = parse_integer(first_byte_pos)?;
273    let last_byte_pos = parse_integer(last_byte_pos)?;
274
275    // We don't support unknown lengths.
276    let complete_len = if complete_len == b"*" {
277        return Err(Error::UnknownValuesAreNotSupported);
278    } else {
279        parse_integer(complete_len)?
280    };
281
282    Ok(ContentRange::Inclusive { first_byte_pos, last_byte_pos, complete_len })
283}
284
285/// Parse an optional integer.
286fn parse_optional_integer(s: &[u8]) -> Result<Option<u64>, Error> {
287    if s.is_empty() { Ok(None) } else { Ok(Some(parse_integer(s)?)) }
288}
289
290/// Parse an integer.
291///
292///     1*DIGIT
293fn parse_integer(s: &[u8]) -> Result<u64, Error> {
294    let mut iter = s.iter();
295
296    // The value requires at least one digit.
297    let mut value = match iter.next() {
298        Some(ch @ b'0'..=b'9') => (ch - b'0') as u64,
299        _ => return Err(Error::Parse),
300    };
301
302    for ch in iter {
303        match ch {
304            ch @ b'0'..=b'9' => {
305                let digit = (ch - b'0') as u64;
306                value = value
307                    .checked_mul(10)
308                    .ok_or(Error::Overflow)?
309                    .checked_add(digit)
310                    .ok_or(Error::Overflow)?;
311            }
312            _ => return Err(Error::Parse),
313        }
314    }
315
316    Ok(value)
317}
318
319fn split_once(s: &[u8], needle: u8) -> Option<(&[u8], &[u8])> {
320    s.iter().position(|ch| *ch == needle).map(|pos| (&s[..pos], &s[pos + 1..]))
321}
322
323#[cfg(test)]
324mod tests {
325    use super::*;
326    use assert_matches::assert_matches;
327
328    #[test]
329    fn test_range_parses_correctly() {
330        for (header, expected) in [
331            ("bytes=1-", Range::From { first_byte_pos: 1 }),
332            ("bytes=1-15", Range::Inclusive { first_byte_pos: 1, last_byte_pos: 15 }),
333            ("bytes=  \t\t  1-15", Range::Inclusive { first_byte_pos: 1, last_byte_pos: 15 }),
334            ("bytes=-15", Range::Suffix { len: 15 }),
335        ] {
336            let header = HeaderValue::from_static(header);
337            let actual = Range::from_http_range_header(&header).unwrap();
338            assert_eq!(actual, expected);
339        }
340    }
341
342    // We don't support multipart ranges.
343    #[test]
344    fn test_range_does_not_support_multipart_range() {
345        let header = HeaderValue::from_static("bytes=1-15, 20-, -50");
346        assert_matches!(
347            Range::from_http_range_header(&header),
348            Err(Error::MultipartRangesAreUnsupported)
349        );
350    }
351
352    #[test]
353    fn test_parse_range_fails_correctly() {
354        for header in
355            ["", "not-bytes=1-15", "bytes=-", "bytes=", "bytes=A-B", "bytes=1A-2B", "bytes=0x1-0x2"]
356        {
357            let header = HeaderValue::from_static(header);
358            assert_matches!(Range::from_http_range_header(&header), Err(Error::Parse));
359        }
360
361        let header = HeaderValue::from_static("bytes=184467440737095516150-184467440737095516151");
362        assert_matches!(Range::from_http_range_header(&header), Err(Error::Overflow));
363    }
364
365    #[test]
366    fn test_range_to_http_range_header() {
367        for (range, expected) in [
368            (Range::Full, None),
369            (Range::From { first_byte_pos: 5 }, Some(HeaderValue::from_static("bytes=5-"))),
370            (
371                Range::Inclusive { first_byte_pos: 5, last_byte_pos: 10 },
372                Some(HeaderValue::from_static("bytes=5-10")),
373            ),
374            (Range::Suffix { len: 5 }, Some(HeaderValue::from_static("bytes=-5"))),
375        ] {
376            assert_eq!(range.to_http_request_header(), expected,)
377        }
378    }
379
380    #[test]
381    fn test_content_range_from_http_content_length_parses_correctly() {
382        for (header, expected) in [
383            ("0", ContentRange::Full { complete_len: 0 }),
384            ("1234", ContentRange::Full { complete_len: 1234 }),
385        ] {
386            let header = HeaderValue::from_static(header);
387            let actual = ContentRange::from_http_content_length_header(&header).unwrap();
388            assert_eq!(actual, expected);
389        }
390    }
391
392    #[test]
393    fn test_content_range_from_http_content_length_fails_correctly() {
394        for header in ["", "abcd", "123abc", "abc123"] {
395            let header = HeaderValue::from_static(header);
396            assert_matches!(
397                ContentRange::from_http_content_length_header(&header),
398                Err(Error::Parse)
399            );
400        }
401
402        let header = HeaderValue::from_static("184467440737095516150");
403        assert_matches!(
404            ContentRange::from_http_content_length_header(&header),
405            Err(Error::Overflow)
406        );
407    }
408
409    #[test]
410    fn test_content_range_from_http_content_range_parses_correctly() {
411        {
412            let (header, expected) = (
413                "bytes 1-5/10",
414                ContentRange::Inclusive { first_byte_pos: 1, last_byte_pos: 5, complete_len: 10 },
415            );
416            let header = HeaderValue::from_static(header);
417            let actual = ContentRange::from_http_content_range_header(&header).unwrap();
418            assert_eq!(actual, expected);
419        }
420    }
421
422    // We do not support Content-Range headers with unknown length.
423    #[test]
424    fn test_content_range_does_not_support_unknown_complete_length() {
425        let header = HeaderValue::from_static("bytes 1-15/*");
426        assert_matches!(
427            ContentRange::from_http_content_range_header(&header),
428            Err(Error::UnknownValuesAreNotSupported)
429        );
430    }
431
432    #[test]
433    fn test_content_range_from_http_content_range_fails_correctly() {
434        for header in ["", "bytes -/10", "not-bytes 1-5/10", "bytes 0x1-0x2/0x3"] {
435            let header = HeaderValue::from_static(header);
436            assert_matches!(
437                ContentRange::from_http_content_range_header(&header),
438                Err(Error::Parse)
439            );
440        }
441
442        let header = HeaderValue::from_static(
443            "bytes 184467440737095516150-184467440737095516151/184467440737095516152",
444        );
445        assert_matches!(
446            ContentRange::from_http_content_range_header(&header),
447            Err(Error::Overflow)
448        );
449    }
450
451    #[test]
452    fn test_content_range_content_len() {
453        for (range, expected) in [
454            (ContentRange::Full { complete_len: 10 }, 10),
455            (ContentRange::Inclusive { first_byte_pos: 1, last_byte_pos: 5, complete_len: 10 }, 5),
456            (ContentRange::Inclusive { first_byte_pos: 1, last_byte_pos: 1, complete_len: 10 }, 1),
457            (ContentRange::Inclusive { first_byte_pos: 5, last_byte_pos: 1, complete_len: 10 }, 0),
458        ] {
459            assert_eq!(range.content_len(), expected, "{range:?}");
460        }
461    }
462
463    #[test]
464    fn test_content_range_total_len() {
465        for (range, expected) in [
466            (ContentRange::Full { complete_len: 10 }, 10),
467            (ContentRange::Inclusive { first_byte_pos: 1, last_byte_pos: 5, complete_len: 10 }, 10),
468            (ContentRange::Inclusive { first_byte_pos: 1, last_byte_pos: 1, complete_len: 10 }, 10),
469            (ContentRange::Inclusive { first_byte_pos: 5, last_byte_pos: 1, complete_len: 10 }, 10),
470        ] {
471            assert_eq!(range.total_len(), expected, "{range:?}");
472        }
473    }
474
475    #[test]
476    fn test_content_range_to_http_content_range_header() {
477        for (range, expected) in [
478            (ContentRange::Full { complete_len: 1234 }, None),
479            (
480                ContentRange::Inclusive {
481                    first_byte_pos: 5,
482                    last_byte_pos: 10,
483                    complete_len: 1234,
484                },
485                Some(HeaderValue::from_static("bytes 5-10/1234")),
486            ),
487        ] {
488            assert_eq!(range.to_http_content_range_header(), expected, "{range:?}");
489        }
490    }
491
492    #[test]
493    fn test_content_length_contains_range_full() {
494        assert!(ContentLength::new(0).contains_range(Range::Full));
495        assert!(ContentLength::new(100).contains_range(Range::Full));
496    }
497
498    #[test]
499    fn test_content_length_contains_range_from() {
500        assert!(ContentLength::new(1).contains_range(Range::From { first_byte_pos: 0 }));
501        assert!(ContentLength::new(100).contains_range(Range::From { first_byte_pos: 50 }));
502        assert!(ContentLength::new(100).contains_range(Range::From { first_byte_pos: 99 }));
503
504        assert!(!ContentLength::new(0).contains_range(Range::From { first_byte_pos: 0 }));
505        assert!(!ContentLength::new(100).contains_range(Range::From { first_byte_pos: 100 }),);
506        assert!(!ContentLength::new(100).contains_range(Range::From { first_byte_pos: 150 }),);
507    }
508
509    #[test]
510    fn test_content_length_contains_range_inclusive() {
511        assert!(
512            ContentLength::new(1)
513                .contains_range(Range::Inclusive { first_byte_pos: 0, last_byte_pos: 0 })
514        );
515        assert!(
516            ContentLength::new(100)
517                .contains_range(Range::Inclusive { first_byte_pos: 0, last_byte_pos: 99 })
518        );
519        assert!(
520            ContentLength::new(100)
521                .contains_range(Range::Inclusive { first_byte_pos: 50, last_byte_pos: 60 })
522        );
523
524        assert!(
525            !ContentLength::new(0)
526                .contains_range(Range::Inclusive { first_byte_pos: 0, last_byte_pos: 0 })
527        );
528        assert!(
529            !ContentLength::new(100)
530                .contains_range(Range::Inclusive { first_byte_pos: 0, last_byte_pos: 100 })
531        );
532        assert!(
533            !ContentLength::new(100)
534                .contains_range(Range::Inclusive { first_byte_pos: 95, last_byte_pos: 105 })
535        );
536        assert!(
537            !ContentLength::new(100)
538                .contains_range(Range::Inclusive { first_byte_pos: 95, last_byte_pos: 105 })
539        );
540        assert!(
541            !ContentLength::new(100)
542                .contains_range(Range::Inclusive { first_byte_pos: 105, last_byte_pos: 115 })
543        );
544    }
545
546    #[test]
547    fn test_content_contains_range_suffix() {
548        assert!(ContentLength::new(0).contains_range(Range::Suffix { len: 0 }),);
549        assert!(ContentLength::new(100).contains_range(Range::Suffix { len: 50 }),);
550        assert!(ContentLength::new(100).contains_range(Range::Suffix { len: 100 }),);
551
552        assert!(!ContentLength::new(100).contains_range(Range::Suffix { len: 150 }),);
553    }
554}
fuchsia_repo/range.rs

fuchsia_repo/
range.rs
