parse_net/
list.rs

1//! The `#rule` lists of RFC 9110 section 5.6.1, including several field lines
2//! read as one list (section 5.3).
3//!
4//! A comma ends an element only outside quoted strings and comments, so
5//! `a="x,y", b` is two elements. Elements are yielded trimmed of OWS, as raw
6//! bytes; the grammar of each element (a token, `token;params`, a media
7//! range) is the caller's.
8//!
9//! # Examples
10//!
11//! ```
12//! use parse_net::{self as pn, Limits};
13//!
14//! let l = pn::list(b"a, \"b,c\" , , (d, e) f,")?;
15//! let all: Vec<&[u8]> = l.iter().collect();
16//! assert_eq!(all, [&b"a"[..], b"\"b,c\"", b"(d, e) f"]);
17//!
18//! let lines: [&[u8]; 3] = [b"gzip", b"", b"br, zstd"];
19//! let c = pn::list::combined(lines, &Limits::DEFAULT)?;
20//! assert_eq!(c.iter().collect::<Vec<_>>(), [&b"gzip"[..], b"br", b"zstd"]);
21//! # Ok::<(), pn::ParseError>(())
22//! ```
23
24use crate::{
25    class,
26    error::{ErrorKind, Result, err},
27    limits::Limits,
28    scan::control_kind,
29    text::{self, comment_end, parse_quoted, trim_ows},
30};
31
32/// Counters carried across the lines of one field.
33#[derive(Clone, Copy, Default)]
34struct Budget {
35    members: usize,
36    empties: usize,
37}
38
39/// Whether `value` holds no quoted string and no comment, so a plain comma
40/// search finds every element boundary.
41#[inline]
42fn is_simple(value: &[u8]) -> bool {
43    !value.iter().any(|&b| matches!(b, b'"' | b'(' | b')'))
44}
45
46/// Accounts for the segment `value[start..end]` (an element or an empty
47/// one) and calls `f` for a non-empty element.
48#[inline]
49fn segment<'a>(
50    value: &'a [u8],
51    start: usize,
52    end: usize,
53    limits: &Limits,
54    budget: &mut Budget,
55    f: &mut impl FnMut(&'a [u8]),
56) -> Result<()> {
57    let raw = value.get(start..end).unwrap_or(&[]);
58    let element = trim_ows(raw);
59    if element.is_empty() {
60        // An empty value has no elements, not one empty element.
61        if !(end == value.len() && start == 0) {
62            budget.empties += 1;
63            if budget.empties > usize::from(limits.empty_elements) {
64                return err(ErrorKind::TooManyEmptyElements, end);
65            }
66        }
67    } else {
68        budget.members += 1;
69        if budget.members > usize::from(limits.list_members) {
70            return err(ErrorKind::TooManyMembers, start + text::skip_ows(raw));
71        }
72        f(element);
73    }
74    Ok(())
75}
76
77/// Validates `value` as a list and calls `f` for each non-empty element, in
78/// one pass with one table lookup per ordinary byte. Returns whether the
79/// value was simple (no quoted string, no comment).
80fn walk<'a>(
81    value: &'a [u8],
82    limits: &Limits,
83    budget: &mut Budget,
84    mut f: impl FnMut(&'a [u8]),
85) -> Result<bool> {
86    let mut simple = true;
87    let mut start = 0usize;
88    let mut i = 0usize;
89    loop {
90        let rest = value.get(i..).unwrap_or(&[]);
91        i += rest
92            .iter()
93            .position(|&b| !class::is_list_plain(b))
94            .unwrap_or(rest.len());
95        match value.get(i) {
96            None => {
97                segment(value, start, i, limits, budget, &mut f)?;
98                return Ok(simple);
99            }
100            Some(b',') => {
101                segment(value, start, i, limits, budget, &mut f)?;
102                i += 1;
103                start = i;
104            }
105            Some(b'"') => {
106                simple = false;
107                let rest = value.get(i..).unwrap_or(&[]);
108                let (_, used) = parse_quoted(rest).map_err(|e| e.shifted(i))?;
109                i += used;
110            }
111            Some(b'(') => {
112                simple = false;
113                let (end, _) = comment_end(value, i, limits)?;
114                i = end;
115            }
116            Some(b')') => return err(ErrorKind::UnbalancedComment, i),
117            // Every byte that is not plain and not a delimiter is a control.
118            Some(&b) => return err(control_kind(b), i),
119        }
120    }
121}
122
123/// Parses `value` as a list with the default [`Limits`].
124///
125/// # Errors
126///
127/// As [`parse`].
128///
129/// # Examples
130///
131/// ```
132/// let codings: Vec<&[u8]> = parse_net::list(b"gzip, deflate;q=0.5")?.iter().collect();
133/// assert_eq!(codings, [&b"gzip"[..], b"deflate;q=0.5"]);
134/// # Ok::<(), parse_net::ParseError>(())
135/// ```
136pub fn list(value: &[u8]) -> Result<List<'_>> {
137    parse(value, &Limits::DEFAULT)
138}
139
140/// Parses `value` as a list.
141///
142/// The whole value is validated: every byte as a field value (RFC 9110
143/// section 5.5), quoted strings terminated with valid quoted pairs, comments
144/// balanced within the depth limit. Empty elements are skipped, up to
145/// [`Limits::max_empty_elements`] (RFC 9110 section 5.6.1.2).
146///
147/// # Errors
148///
149/// [`ErrorKind::BareCr`], [`ErrorKind::LineFeed`], [`ErrorKind::Nul`],
150/// [`ErrorKind::Control`]; [`ErrorKind::UnterminatedQuote`],
151/// [`ErrorKind::InvalidQuotedPair`]; [`ErrorKind::UnbalancedComment`],
152/// [`ErrorKind::CommentTooDeep`]; [`ErrorKind::TooManyEmptyElements`] at the
153/// separator that exceeded the budget; [`ErrorKind::TooManyMembers`] at the
154/// element beyond [`Limits::max_list_members`].
155///
156/// # Examples
157///
158/// ```
159/// use parse_net::{list, ErrorKind, Limits};
160///
161/// let l = list::parse(b"a, b", &Limits::DEFAULT)?;
162/// assert_eq!(l.len(), 2);
163/// assert_eq!(list::parse(b"a, \"b", &Limits::DEFAULT).unwrap_err().kind(), ErrorKind::UnterminatedQuote);
164/// # Ok::<(), parse_net::ParseError>(())
165/// ```
166pub fn parse<'a>(value: &'a [u8], limits: &Limits) -> Result<List<'a>> {
167    let mut budget = Budget::default();
168    let simple = walk(value, limits, &mut budget, |_| {})?;
169    Ok(List {
170        value,
171        // The member limit is a u16, so the count fits.
172        count: u32::try_from(budget.members).unwrap_or(u32::MAX),
173        simple,
174    })
175}
176
177/// Validates `value` and calls `f` for each element in the same pass, then
178/// returns the element count.
179///
180/// On error, `f` has seen the elements before the failure.
181///
182/// # Errors
183///
184/// As [`parse`].
185///
186/// # Examples
187///
188/// ```
189/// use parse_net::{list, Limits};
190///
191/// let mut longest = 0;
192/// let n = list::for_each(b"gzip, br, zstd", &Limits::DEFAULT, |e| longest = longest.max(e.len()))?;
193/// assert_eq!((n, longest), (3, 4));
194/// # Ok::<(), parse_net::ParseError>(())
195/// ```
196pub fn for_each<'a>(value: &'a [u8], limits: &Limits, f: impl FnMut(&'a [u8])) -> Result<usize> {
197    let mut budget = Budget::default();
198    let _simple = walk(value, limits, &mut budget, f)?;
199    Ok(budget.members)
200}
201
202/// Validates several field lines of one name as one list (RFC 9110 section
203/// 5.3), as if joined by `", "`, without joining them.
204///
205/// An empty line adds nothing. An element never spans two lines, so a quoted
206/// string still open at the end of a line is refused. The empty-element and
207/// member budgets count across all lines.
208///
209/// # Errors
210///
211/// As [`parse`], with [`ParseError::line`](crate::ParseError::line) set to the
212/// failing line.
213///
214/// # Examples
215///
216/// ```
217/// use parse_net::{list, Limits};
218///
219/// let lines: [&[u8]; 2] = [b"a, \"x", b"y\""];
220/// assert!(list::combined(lines, &Limits::DEFAULT).is_err());
221/// ```
222pub fn combined<'a, I>(lines: I, limits: &Limits) -> Result<CombinedList<'a, I::IntoIter>>
223where
224    I: IntoIterator<Item = &'a [u8]>,
225    I::IntoIter: Clone,
226{
227    let lines = lines.into_iter();
228    let mut budget = Budget::default();
229    for (n, line) in lines.clone().enumerate() {
230        let _simple = walk(line, limits, &mut budget, |_| {}).map_err(|e| e.on_line(n))?;
231    }
232    Ok(CombinedList {
233        lines,
234        count: budget.members,
235        _value: core::marker::PhantomData,
236    })
237}
238
239/// Whether any element of any line equals `token`, ignoring ASCII case.
240///
241/// For `Connection: keep-alive, Upgrade` and `Upgrade: websocket`. A line
242/// that fails to parse counts as not containing the token (fail closed).
243///
244/// # Examples
245///
246/// ```
247/// use parse_net::list::contains_token;
248///
249/// assert!(contains_token([&b"keep-alive, Upgrade"[..]], b"upgrade"));
250/// assert!(!contains_token([&b"keep-alive, \"upgrade"[..]], b"upgrade"));
251/// ```
252pub fn contains_token<'a, I>(lines: I, token: &[u8]) -> bool
253where
254    I: IntoIterator<Item = &'a [u8]>,
255{
256    lines.into_iter().any(|line| {
257        parse(line, &Limits::DEFAULT).is_ok_and(|l| l.iter().any(|e| e.eq_ignore_ascii_case(token)))
258    })
259}
260
261/// A validated list. Iterating it cannot fail.
262///
263/// # Examples
264///
265/// ```
266/// let l = parse_net::list(b"gzip, , br")?;
267/// assert_eq!(l.len(), 2);
268/// assert_eq!(l.iter().collect::<Vec<_>>(), [&b"gzip"[..], b"br"]);
269/// # Ok::<(), parse_net::ParseError>(())
270/// ```
271#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
272pub struct List<'a> {
273    value: &'a [u8],
274    count: u32,
275    simple: bool,
276}
277
278impl<'a> List<'a> {
279    /// The elements, in order, each trimmed of OWS.
280    ///
281    /// # Examples
282    ///
283    /// ```
284    /// let l = parse_net::list(b"a, \"b, c\"")?;
285    /// let mut it = l.iter();
286    /// assert_eq!(it.next(), Some(&b"a"[..]));
287    /// assert_eq!(it.next(), Some(&b"\"b, c\""[..]));
288    /// assert_eq!(it.next(), None);
289    /// # Ok::<(), parse_net::ParseError>(())
290    /// ```
291    #[must_use]
292    pub fn iter(&self) -> Elements<'a> {
293        Elements {
294            rest: self.value,
295            remaining: self.count as usize,
296            simple: self.simple,
297        }
298    }
299
300    /// The number of elements.
301    ///
302    /// # Examples
303    ///
304    /// ```
305    /// assert_eq!(parse_net::list(b"a, , b,")?.len(), 2);
306    /// # Ok::<(), parse_net::ParseError>(())
307    /// ```
308    #[must_use]
309    pub const fn len(&self) -> usize {
310        self.count as usize
311    }
312
313    /// Whether the list has no elements.
314    ///
315    /// # Examples
316    ///
317    /// ```
318    /// assert!(parse_net::list(b" , ")?.is_empty());
319    /// assert!(!parse_net::list(b"a")?.is_empty());
320    /// # Ok::<(), parse_net::ParseError>(())
321    /// ```
322    #[must_use]
323    pub const fn is_empty(&self) -> bool {
324        self.count == 0
325    }
326}
327
328impl<'a> IntoIterator for List<'a> {
329    type Item = &'a [u8];
330    type IntoIter = Elements<'a>;
331
332    fn into_iter(self) -> Elements<'a> {
333        self.iter()
334    }
335}
336
337/// The index of the first comma of `s` outside quoted strings and comments.
338/// `s` has been validated, so quotes and comments are well formed.
339fn top_level_comma(s: &[u8]) -> Option<usize> {
340    let mut i = 0usize;
341    let mut depth = 0u32;
342    let mut quoted = false;
343    while let Some(&b) = s.get(i) {
344        match b {
345            b'\\' if quoted || depth > 0 => i += 1,
346            b'"' if depth == 0 => quoted = !quoted,
347            b'(' if !quoted => depth += 1,
348            b')' if !quoted => depth = depth.saturating_sub(1),
349            b',' if !quoted && depth == 0 => return Some(i),
350            _ => {}
351        }
352        i += 1;
353    }
354    None
355}
356
357/// The elements of a validated list.
358///
359/// # Examples
360///
361/// ```
362/// let mut e = parse_net::list(b"gzip, br")?.iter();
363/// assert_eq!(e.len(), 2);
364/// assert_eq!(e.next(), Some(&b"gzip"[..]));
365/// assert_eq!(e.len(), 1);
366/// # Ok::<(), parse_net::ParseError>(())
367/// ```
368#[derive(Clone, Debug)]
369pub struct Elements<'a> {
370    rest: &'a [u8],
371    remaining: usize,
372    simple: bool,
373}
374
375impl<'a> Iterator for Elements<'a> {
376    type Item = &'a [u8];
377
378    fn next(&mut self) -> Option<&'a [u8]> {
379        while self.remaining > 0 && !self.rest.is_empty() {
380            let end = if self.simple {
381                self.rest.iter().position(|&b| b == b',')
382            } else {
383                top_level_comma(self.rest)
384            }
385            .unwrap_or(self.rest.len());
386            let element = trim_ows(self.rest.get(..end).unwrap_or(&[]));
387            self.rest = self.rest.get(end + 1..).unwrap_or(&[]);
388            if !element.is_empty() {
389                self.remaining -= 1;
390                return Some(element);
391            }
392        }
393        None
394    }
395
396    fn size_hint(&self) -> (usize, Option<usize>) {
397        (self.remaining, Some(self.remaining))
398    }
399}
400
401impl ExactSizeIterator for Elements<'_> {}
402
403/// Several validated field lines read as one list.
404///
405/// # Examples
406///
407/// ```
408/// use parse_net::{list, Limits};
409///
410/// let lines: [&[u8]; 2] = [b"gzip", b"br, zstd"];
411/// let c = list::combined(lines, &Limits::DEFAULT)?;
412/// assert_eq!(c.len(), 3);
413/// assert!(c.iter().any(|e| e == b"zstd"));
414/// # Ok::<(), parse_net::ParseError>(())
415/// ```
416#[derive(Clone, Debug)]
417pub struct CombinedList<'a, I> {
418    lines: I,
419    count: usize,
420    _value: core::marker::PhantomData<&'a [u8]>,
421}
422
423impl<'a, I: Iterator<Item = &'a [u8]> + Clone> CombinedList<'a, I> {
424    /// The elements of every line, in order.
425    ///
426    /// # Examples
427    ///
428    /// ```
429    /// use parse_net::{list, Limits};
430    ///
431    /// let lines: [&[u8]; 2] = [b"gzip", b"br, zstd"];
432    /// let c = list::combined(lines, &Limits::DEFAULT)?;
433    /// assert_eq!(c.iter().collect::<Vec<_>>(), [&b"gzip"[..], b"br", b"zstd"]);
434    /// # Ok::<(), parse_net::ParseError>(())
435    /// ```
436    #[must_use]
437    pub fn iter(&self) -> CombinedElements<'a, I> {
438        CombinedElements {
439            lines: self.lines.clone(),
440            current: Elements {
441                rest: &[],
442                remaining: 0,
443                simple: true,
444            },
445            remaining: self.count,
446        }
447    }
448
449    /// The number of elements across all lines.
450    ///
451    /// # Examples
452    ///
453    /// ```
454    /// use parse_net::{list, Limits};
455    ///
456    /// let lines: [&[u8]; 3] = [b"a, b", b"", b"c"];
457    /// assert_eq!(list::combined(lines, &Limits::DEFAULT)?.len(), 3);
458    /// # Ok::<(), parse_net::ParseError>(())
459    /// ```
460    #[must_use]
461    pub const fn len(&self) -> usize {
462        self.count
463    }
464
465    /// Whether no line has an element.
466    ///
467    /// # Examples
468    ///
469    /// ```
470    /// use parse_net::{list, Limits};
471    ///
472    /// let lines: [&[u8]; 2] = [b"", b" , "];
473    /// assert!(list::combined(lines, &Limits::DEFAULT)?.is_empty());
474    /// # Ok::<(), parse_net::ParseError>(())
475    /// ```
476    #[must_use]
477    pub const fn is_empty(&self) -> bool {
478        self.count == 0
479    }
480}
481
482/// The elements of a [`CombinedList`].
483///
484/// # Examples
485///
486/// ```
487/// use parse_net::{list, Limits};
488///
489/// let lines: [&[u8]; 2] = [b"gzip", b"br"];
490/// let mut it = list::combined(lines, &Limits::DEFAULT)?.iter();
491/// assert_eq!(it.next(), Some(&b"gzip"[..]));
492/// assert_eq!(it.next(), Some(&b"br"[..]));
493/// assert_eq!(it.next(), None);
494/// # Ok::<(), parse_net::ParseError>(())
495/// ```
496#[derive(Clone, Debug)]
497pub struct CombinedElements<'a, I> {
498    lines: I,
499    current: Elements<'a>,
500    remaining: usize,
501}
502
503impl<'a, I: Iterator<Item = &'a [u8]>> Iterator for CombinedElements<'a, I> {
504    type Item = &'a [u8];
505
506    fn next(&mut self) -> Option<&'a [u8]> {
507        while self.remaining > 0 {
508            if let Some(e) = self.current.next() {
509                self.remaining -= 1;
510                return Some(e);
511            }
512            let line = self.lines.next()?;
513            // The line was validated with the same rules; `usize::MAX` lets
514            // the walker run to the line's end.
515            self.current = Elements {
516                rest: line,
517                remaining: usize::MAX,
518                simple: is_simple(line),
519            };
520        }
521        None
522    }
523
524    fn size_hint(&self) -> (usize, Option<usize>) {
525        (self.remaining, Some(self.remaining))
526    }
527}
528
529impl<'a, I: Iterator<Item = &'a [u8]>> ExactSizeIterator for CombinedElements<'a, I> {}
530
531#[cfg(test)]
532mod tests {
533    use std::{vec, vec::Vec};
534
535    use super::*;
536
537    fn all(v: &[u8]) -> Vec<&[u8]> {
538        list(v).unwrap().iter().collect()
539    }
540
541    #[test]
542    fn test_list_edge_cases() {
543        assert!(all(b"").is_empty());
544        assert!(all(b"   ").is_empty());
545        assert!(all(b",").is_empty());
546        assert!(all(b", ,").is_empty());
547        assert_eq!(all(b"a,"), [b"a"]);
548        assert_eq!(all(b",a"), [b"a"]);
549        assert_eq!(all(b"a,,b"), [&b"a"[..], b"b"]);
550        assert_eq!(all(b"a, \"b,c\""), [&b"a"[..], b"\"b,c\""]);
551        assert_eq!(all(b"a, (b,c)"), [&b"a"[..], b"(b,c)"]);
552        assert_eq!(all(b"a;q=1 , b"), [&b"a;q=1"[..], b"b"]);
553        assert_eq!(all(b"a=\"x\\\",y\", b"), [&b"a=\"x\\\",y\""[..], b"b"]);
554        assert_eq!(all(b"(a\\)b,c), d"), [&b"(a\\)b,c)"[..], b"d"]);
555    }
556
557    #[test]
558    fn test_list_comma_in_quotes_is_one_element() {
559        assert_eq!(all(b"filename=\"a,b.txt\""), [&b"filename=\"a,b.txt\""[..]]);
560    }
561
562    #[test]
563    fn test_list_empty_element_budget() {
564        // "a" and "b" around 17 commas leave 16 empty elements; 18 leave 17.
565        let mut sixteen = vec![b'a'];
566        sixteen.extend([b','; 17]);
567        sixteen.push(b'b');
568        assert_eq!(all(&sixteen), [&b"a"[..], b"b"]);
569        let mut seventeen = vec![b'a'];
570        seventeen.extend([b','; 18]);
571        seventeen.push(b'b');
572        let e = list(&seventeen).unwrap_err();
573        assert_eq!(
574            (e.kind(), e.offset()),
575            (ErrorKind::TooManyEmptyElements, 18)
576        );
577    }
578
579    #[test]
580    fn test_list_member_budget() {
581        let mut v = Vec::new();
582        for i in 0..1025 {
583            if i > 0 {
584                v.extend_from_slice(b", ");
585            }
586            v.push(b'a');
587        }
588        assert_eq!(list(&v[..v.len() - 3]).unwrap().len(), 1024);
589        assert_eq!(list(&v).unwrap_err().kind(), ErrorKind::TooManyMembers);
590        let e = parse(b"a, b, c", &Limits::DEFAULT.max_list_members(2)).unwrap_err();
591        assert_eq!(e.offset(), 6);
592    }
593
594    #[test]
595    fn test_list_refuses_bad_bytes_and_structure() {
596        assert_eq!(list(b"a\rb").unwrap_err().kind(), ErrorKind::BareCr);
597        assert_eq!(
598            list(b"a, \"b").unwrap_err().kind(),
599            ErrorKind::UnterminatedQuote
600        );
601        assert_eq!(
602            list(b"a)").unwrap_err().kind(),
603            ErrorKind::UnbalancedComment
604        );
605        assert_eq!(
606            list(b"(a").unwrap_err().kind(),
607            ErrorKind::UnbalancedComment
608        );
609        let e = list(b"ab, \"c\x01\"").unwrap_err();
610        assert_eq!((e.kind(), e.offset()), (ErrorKind::Control, 6));
611    }
612
613    #[test]
614    fn test_combined_lines() {
615        let lines: [&[u8]; 3] = [b"a, b", b"", b"c"];
616        let c = combined(lines, &Limits::DEFAULT).unwrap();
617        assert_eq!(c.len(), 3);
618        assert_eq!(c.iter().collect::<Vec<_>>(), [&b"a"[..], b"b", b"c"]);
619        assert_eq!(c.iter().len(), 3);
620        let bad: [&[u8]; 2] = [b"a", b"\"open"];
621        let e = combined(bad, &Limits::DEFAULT).unwrap_err();
622        assert_eq!((e.kind(), e.line()), (ErrorKind::UnterminatedQuote, 1));
623        let empty: [&[u8]; 0] = [];
624        assert!(combined(empty, &Limits::DEFAULT).unwrap().is_empty());
625    }
626
627    #[test]
628    fn test_combined_budgets_count_across_lines() {
629        let l = Limits::DEFAULT.max_list_members(2);
630        let lines: [&[u8]; 2] = [b"a", b"b, c"];
631        let e = combined(lines, &l).unwrap_err();
632        assert_eq!(
633            (e.kind(), e.line(), e.offset()),
634            (ErrorKind::TooManyMembers, 1, 3)
635        );
636    }
637
638    #[test]
639    fn test_combined_equals_joined_at_every_comma() {
640        let value = b"a, \"b,c\", (d,e), f;g=\"h\", i";
641        let whole = all(value);
642        let mut commas = Vec::new();
643        let mut from = 0;
644        while let Some(i) = top_level_comma(&value[from..]) {
645            commas.push(from + i);
646            from += i + 1;
647        }
648        assert_eq!(commas.len(), 4);
649        for &split in &commas {
650            let lines: [&[u8]; 2] = [&value[..split], &value[split + 1..]];
651            let c = combined(lines, &Limits::DEFAULT).unwrap();
652            assert_eq!(c.iter().collect::<Vec<_>>(), whole, "split at {split}");
653        }
654    }
655
656    #[test]
657    fn test_contains_token_fails_closed() {
658        assert!(contains_token(
659            [&b"close"[..], b"keep-alive, Upgrade"],
660            b"upgrade"
661        ));
662        assert!(!contains_token([&b"upgrade\r"[..]], b"upgrade"));
663        let none: [&[u8]; 0] = [];
664        assert!(!contains_token(none, b"x"));
665    }
666
667    #[test]
668    fn test_for_each_sees_every_element() {
669        let mut seen = vec![];
670        let n = for_each(b"a, b ,c", &Limits::DEFAULT, |e| seen.push(e)).unwrap();
671        assert_eq!((n, seen), (3, vec![&b"a"[..], b"b", b"c"]));
672    }
673}
parse_net/list.rs

parse_net/
list.rs
