Skip to main content

rpc_io/
framing.rs

1//! Message framing: how message bodies are cut out of a byte stream and put
2//! back into one.
3//!
4//! The [`Decoder`] is sans-IO: it owns a buffer, says where the next bytes
5//! should go ([`Decoder::space`]), and returns complete message bodies
6//! ([`Decoder::next_frame`]). Whoever owns the stream does the reading, so the
7//! same decoder serves a blocking `Read`, a non-blocking socket, or bytes that
8//! arrive any other way.
9
10use alloc::vec::Vec;
11use core::{fmt, ops::Range};
12
13use crate::limits::Limits;
14
15/// Bytes offered for each read, and the read-ahead past a message's end.
16pub const READ_CHUNK: usize = 8 * 1024;
17
18/// How messages are delimited on a byte stream.
19///
20/// `#[non_exhaustive]`: HTTP bodies and WebSocket messages are planned (see
21/// the roadmap).
22///
23/// # Examples
24///
25/// ```
26/// use rpc_io::Framing;
27///
28/// let mut out = Vec::new();
29/// Framing::ContentLength.encode(br#"{"jsonrpc":"2.0","method":"x"}"#, &mut out);
30/// assert!(out.starts_with(b"Content-Length: 30\r\n\r\n{"));
31///
32/// out.clear();
33/// Framing::Newline.encode(b"{\n}", &mut out);
34/// assert_eq!(out, b"{ }\n");
35/// ```
36#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
37#[non_exhaustive]
38pub enum Framing {
39    /// `Content-Length: <n>\r\n\r\n` and then `n` bytes of body: the base
40    /// protocol of LSP and DAP. Other headers (`Content-Type`) are accepted and
41    /// ignored; header names match case-insensitively; a bare `\n` line end is
42    /// accepted for `\r\n`. Blank lines before a header section (stray line
43    /// ends between messages) are skipped and do not count against
44    /// [`Limits::max_header_bytes`]: each is consumed as soon as its line end
45    /// arrives, so they cost no memory, and a header section is measured the
46    /// same however the input was split.
47    ContentLength,
48    /// One message per line, ended by `\n` (an `\r` before it is dropped):
49    /// MCP's stdio transport, and JSON Lines. Lines holding only whitespace are
50    /// skipped, but every line counts against
51    /// [`Limits::max_message_bytes`], blank or not: a line over it is
52    /// [`FrameError::TooLarge`] (with `length: None`) however the input was
53    /// split into reads. Blank lines are consumed as soon as their `\n`
54    /// arrives, so a run of them costs no memory.
55    Newline,
56}
57
58impl Framing {
59    /// Appends `body` to `out` as one framed message.
60    ///
61    /// For [`Newline`](Framing::Newline), every `\r` and `\n` in `body` is
62    /// written as a space. In valid JSON line breaks can only be whitespace
63    /// (strings cannot contain them raw), so the message means the same and
64    /// stays on one line; text that is not JSON still cannot split the frame.
65    ///
66    /// # Examples
67    ///
68    /// ```
69    /// use rpc_io::Framing;
70    ///
71    /// let mut out = Vec::new();
72    /// Framing::ContentLength.encode(b"{}", &mut out);
73    /// assert_eq!(out, b"Content-Length: 2\r\n\r\n{}");
74    /// ```
75    pub fn encode(self, body: &[u8], out: &mut Vec<u8>) {
76        match self {
77            Framing::ContentLength => {
78                out.reserve(body.len() + 40);
79                out.extend_from_slice(b"Content-Length: ");
80                let (digits, at) = decimal(body.len() as u64);
81                out.extend_from_slice(&digits[at..]);
82                out.extend_from_slice(b"\r\n\r\n");
83                out.extend_from_slice(body);
84            }
85            Framing::Newline => {
86                out.reserve(body.len() + 1);
87                let mut rest = body;
88                while let Some(at) = find_line_break(rest) {
89                    out.extend_from_slice(&rest[..at]);
90                    out.push(b' ');
91                    rest = &rest[at + 1..];
92                }
93                out.extend_from_slice(rest);
94                out.push(b'\n');
95            }
96        }
97    }
98
99    /// A [`Decoder`] for this framing under `limits`.
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// use rpc_io::{Framing, Limits};
105    ///
106    /// let mut decoder = Framing::Newline.decoder(&Limits::new());
107    /// let taken = decoder.feed(b"{\"a\":1}\n{\"b\"");
108    /// assert_eq!(taken, 12);
109    /// assert_eq!(decoder.next_frame(), Ok(Some(&b"{\"a\":1}"[..])));
110    /// assert_eq!(decoder.next_frame(), Ok(None)); // the second line is not complete yet
111    /// ```
112    #[must_use]
113    pub fn decoder(self, limits: &Limits) -> Decoder {
114        Decoder::new(self, limits)
115    }
116}
117
118/// Why a byte stream could not be cut into messages.
119///
120/// Only [`TooLarge`](FrameError::TooLarge) is recoverable: the decoder has
121/// skipped (or is skipping) the oversized message without buffering it, and
122/// the next message can be read. Every other error leaves the stream with no
123/// reliable message boundary, so the decoder stops and returns the same error
124/// from then on.
125///
126/// # Examples
127///
128/// ```
129/// use rpc_io::{FrameError, Framing, Limits};
130///
131/// let mut decoder = Framing::ContentLength.decoder(&Limits::new());
132/// decoder.feed(b"Content-Length: 1x\r\n\r\n");
133/// assert_eq!(decoder.next_frame(), Err(FrameError::InvalidContentLength));
134/// assert!(!FrameError::InvalidContentLength.is_recoverable());
135/// ```
136#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
137#[non_exhaustive]
138pub enum FrameError {
139    /// A header section exceeded [`Limits::max_header_bytes`].
140    HeaderTooLarge {
141        /// The limit, in bytes.
142        limit: usize,
143    },
144    /// A header section had more than [`Limits::max_headers`] lines.
145    TooManyHeaders {
146        /// The limit, in lines.
147        limit: usize,
148    },
149    /// A header line has no `:`, or its name is not an RFC 9110 token
150    /// (empty, or holding a space, a brace, or another separator).
151    InvalidHeader,
152    /// A header section ended without a `Content-Length` header.
153    MissingContentLength,
154    /// A header section has more than one `Content-Length` header.
155    DuplicateContentLength,
156    /// A `Content-Length` value is not a decimal integer that fits in 64 bits.
157    InvalidContentLength,
158    /// A message exceeded [`Limits::max_message_bytes`]. Recoverable: the
159    /// message is skipped without being buffered.
160    TooLarge {
161        /// The length the header announced; always `None` for a
162        /// newline-delimited line, which is refused as soon as it outgrows the
163        /// limit, before its length is known.
164        length: Option<u64>,
165        /// The limit, in bytes.
166        limit: usize,
167    },
168    /// The stream ended inside a message.
169    Truncated,
170}
171
172impl FrameError {
173    /// Whether the decoder can go on to the next message.
174    ///
175    /// # Examples
176    ///
177    /// ```
178    /// use rpc_io::FrameError;
179    ///
180    /// assert!(FrameError::TooLarge { length: Some(9), limit: 8 }.is_recoverable());
181    /// assert!(!FrameError::Truncated.is_recoverable());
182    /// ```
183    #[must_use]
184    pub const fn is_recoverable(&self) -> bool {
185        matches!(self, FrameError::TooLarge { .. })
186    }
187}
188
189impl fmt::Display for FrameError {
190    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
191        match self {
192            FrameError::HeaderTooLarge { limit } => {
193                write!(f, "a header section is longer than {limit} bytes")
194            }
195            FrameError::TooManyHeaders { limit } => {
196                write!(f, "a header section has more than {limit} lines")
197            }
198            FrameError::InvalidHeader => f.write_str("a header line is not `name: value`"),
199            FrameError::MissingContentLength => {
200                f.write_str("a header section has no `Content-Length`")
201            }
202            FrameError::DuplicateContentLength => {
203                f.write_str("a header section has more than one `Content-Length`")
204            }
205            FrameError::InvalidContentLength => {
206                f.write_str("a `Content-Length` value is not a non-negative decimal integer")
207            }
208            FrameError::TooLarge {
209                length: Some(length),
210                limit,
211            } => write!(
212                f,
213                "a message of {length} bytes exceeds the limit of {limit}"
214            ),
215            FrameError::TooLarge {
216                length: None,
217                limit,
218            } => {
219                write!(f, "a message exceeds the limit of {limit} bytes")
220            }
221            FrameError::Truncated => f.write_str("the stream ended inside a message"),
222        }
223    }
224}
225
226impl core::error::Error for FrameError {}
227
228/// Where the decoder is in the stream.
229#[derive(Clone, Copy, Debug, PartialEq, Eq)]
230enum State {
231    /// Reading a Content-Length header section: lines so far, bytes so far,
232    /// and the length once seen.
233    Headers {
234        lines: usize,
235        bytes: usize,
236        length: Option<u64>,
237    },
238    /// Waiting for a body of `length` bytes, starting at `start`.
239    Body { length: usize },
240    /// Dropping the rest of an oversized Content-Length body.
241    Skip { remaining: u64 },
242    /// Reading a newline-delimited line.
243    Line,
244    /// Dropping the rest of an oversized line, up to its `\n`.
245    Discard,
246}
247
248/// Cuts message bodies out of a byte stream (sans-IO).
249///
250/// Bytes go in through [`space`](Decoder::space) and
251/// [`commit`](Decoder::commit) (read straight into the decoder's buffer, no
252/// extra copy) or [`feed`](Decoder::feed) (copied from a slice); bodies come
253/// out of [`next_frame`](Decoder::next_frame) as slices of the buffer. The
254/// two alternate: the decoder takes more bytes only once `next_frame` has
255/// returned `Ok(None)`, which is what keeps its memory bounded no matter how
256/// the peer sends:
257///
258/// - the buffer never exceeds one message plus [`READ_CHUNK`] bytes of
259///   read-ahead (`max(max_message_bytes + 1, max_header_bytes) + READ_CHUNK`);
260/// - a Content-Length body is reserved as its bytes arrive, never all at once
261///   from the header's word alone;
262/// - an oversized message is skipped as it arrives ([`FrameError::TooLarge`])
263///   rather than buffered;
264/// - lines are scanned once: the search for a line end resumes where the last
265///   one stopped, so a message delivered a byte at a time costs linear work.
266///
267/// # Examples
268///
269/// Reading from any `std::io::Read`:
270///
271/// ```
272/// use std::io::Read;
273/// use rpc_io::{Framing, Limits};
274///
275/// let mut input: &[u8] = b"Content-Length: 2\r\n\r\n{}Content-Length: 4\r\n\r\nnull";
276/// let mut decoder = Framing::ContentLength.decoder(&Limits::new());
277/// let mut bodies = Vec::new();
278/// loop {
279///     while let Some(body) = decoder.next_frame()? {
280///         bodies.push(body.to_vec());
281///     }
282///     let n = input.read(decoder.space()).unwrap_or(0);
283///     if n == 0 {
284///         break;
285///     }
286///     decoder.commit(n);
287/// }
288/// assert_eq!(decoder.finish()?, None); // nothing left over
289/// assert_eq!(bodies, [b"{}".to_vec(), b"null".to_vec()]);
290/// # Ok::<(), rpc_io::FrameError>(())
291/// ```
292#[derive(Clone, Debug)]
293pub struct Decoder {
294    framing: Framing,
295    max_message: usize,
296    max_header_bytes: usize,
297    max_headers: usize,
298    /// Initialized storage; bytes `start..end` are buffered and unconsumed.
299    buf: Vec<u8>,
300    start: usize,
301    end: usize,
302    /// Where the search for the next line end resumes (`start..=end`).
303    scan: usize,
304    state: State,
305    /// Whether `next_frame` has found nothing more since the last commit;
306    /// only then is space offered.
307    drained: bool,
308    /// The fatal error the decoder stopped on.
309    failed: Option<FrameError>,
310}
311
312impl Decoder {
313    /// A decoder for `framing` under `limits`. Allocates nothing until the
314    /// first bytes arrive.
315    ///
316    /// # Examples
317    ///
318    /// ```
319    /// use rpc_io::{Decoder, Framing, Limits};
320    ///
321    /// let decoder = Decoder::new(Framing::Newline, &Limits::new());
322    /// assert_eq!(decoder.buffered(), 0);
323    /// ```
324    #[must_use]
325    pub fn new(framing: Framing, limits: &Limits) -> Self {
326        Self {
327            framing,
328            max_message: limits.max_message_bytes,
329            max_header_bytes: limits.max_header_bytes,
330            max_headers: limits.max_headers,
331            buf: Vec::new(),
332            start: 0,
333            end: 0,
334            scan: 0,
335            state: Self::fresh(framing),
336            drained: true,
337            failed: None,
338        }
339    }
340
341    /// The framing this decoder reads.
342    ///
343    /// # Examples
344    ///
345    /// ```
346    /// use rpc_io::{Framing, Limits};
347    ///
348    /// assert_eq!(Framing::Newline.decoder(&Limits::new()).framing(), Framing::Newline);
349    /// ```
350    #[inline]
351    #[must_use]
352    pub const fn framing(&self) -> Framing {
353        self.framing
354    }
355
356    /// Bytes buffered and not yet returned or skipped.
357    ///
358    /// # Examples
359    ///
360    /// ```
361    /// use rpc_io::{Framing, Limits};
362    ///
363    /// let mut d = Framing::Newline.decoder(&Limits::new());
364    /// d.feed(b"{\"partial\"");
365    /// assert_eq!(d.next_frame(), Ok(None));
366    /// assert_eq!(d.buffered(), 10);
367    /// ```
368    #[inline]
369    #[must_use]
370    pub const fn buffered(&self) -> usize {
371        self.end - self.start
372    }
373
374    /// The most memory the buffer can ever hold under these limits.
375    ///
376    /// # Examples
377    ///
378    /// ```
379    /// use rpc_io::{Framing, Limits, READ_CHUNK};
380    ///
381    /// let limits = Limits::new().with_max_message_bytes(1000).with_max_header_bytes(100);
382    /// assert_eq!(Framing::Newline.decoder(&limits).memory_bound(), 1001 + READ_CHUNK);
383    /// ```
384    #[must_use]
385    pub const fn memory_bound(&self) -> usize {
386        let message = self.max_message.saturating_add(1);
387        let largest = if message > self.max_header_bytes {
388            message
389        } else {
390            self.max_header_bytes
391        };
392        largest.saturating_add(READ_CHUNK)
393    }
394
395    /// Where to put the next bytes read from the stream; follow with
396    /// [`commit`](Decoder::commit).
397    ///
398    /// Empty until [`next_frame`](Decoder::next_frame) has returned
399    /// `Ok(None)` (every complete message taken), and after a fatal error.
400    /// The slice is at least [`READ_CHUNK`] bytes otherwise, more while a large
401    /// body arrives.
402    ///
403    /// # Examples
404    ///
405    /// ```
406    /// use rpc_io::{Framing, Limits};
407    ///
408    /// let mut d = Framing::Newline.decoder(&Limits::new());
409    /// let space = d.space();
410    /// space[..3].copy_from_slice(b"[]\n");
411    /// d.commit(3);
412    /// assert!(d.space().is_empty()); // a message may be ready: take it first
413    /// assert_eq!(d.next_frame(), Ok(Some(&b"[]"[..])));
414    /// assert_eq!(d.next_frame(), Ok(None));
415    /// assert!(!d.space().is_empty());
416    /// ```
417    pub fn space(&mut self) -> &mut [u8] {
418        if !self.drained || self.failed.is_some() {
419            return &mut [];
420        }
421        if self.start == self.end {
422            self.start = 0;
423            self.end = 0;
424            self.scan = 0;
425        }
426        let want = match self.state {
427            State::Body { length } => {
428                let have = self.end - self.start;
429                let need = length.saturating_sub(have);
430                // Grow as the body arrives (doubling), never to the announced
431                // length on the header's word alone.
432                if need <= READ_CHUNK {
433                    READ_CHUNK
434                } else {
435                    need.min(have.max(READ_CHUNK))
436                }
437            }
438            _ => READ_CHUNK,
439        };
440        if self.buf.len() - self.end < want {
441            if self.start > 0 {
442                self.buf.copy_within(self.start..self.end, 0);
443                self.end -= self.start;
444                self.scan -= self.start;
445                self.start = 0;
446            }
447            let missing = want.saturating_sub(self.buf.len() - self.end);
448            if missing > 0 {
449                self.buf.reserve_exact(missing);
450                self.buf.resize(self.buf.len() + missing, 0);
451            }
452        }
453        &mut self.buf[self.end..]
454    }
455
456    /// Records that `n` bytes were written at the start of the last
457    /// [`space`](Decoder::space). Values beyond that space are clamped.
458    ///
459    /// # Examples
460    ///
461    /// ```
462    /// use rpc_io::{Framing, Limits};
463    ///
464    /// let mut d = Framing::Newline.decoder(&Limits::new());
465    /// d.space()[..2].copy_from_slice(b"1\n");
466    /// d.commit(2);
467    /// assert_eq!(d.next_frame(), Ok(Some(&b"1"[..])));
468    /// ```
469    pub fn commit(&mut self, n: usize) {
470        let n = n.min(self.buf.len() - self.end);
471        if n > 0 {
472            self.end += n;
473            self.drained = false;
474        }
475    }
476
477    /// Copies as much of `bytes` as the decoder takes now and returns how many
478    /// it took: zero until [`next_frame`](Decoder::next_frame) has returned
479    /// `Ok(None)`. Feed the rest after taking the messages out.
480    ///
481    /// # Examples
482    ///
483    /// ```
484    /// use rpc_io::{Framing, Limits};
485    ///
486    /// let mut d = Framing::Newline.decoder(&Limits::new());
487    /// let mut input: &[u8] = b"1\n2\n3\n";
488    /// let mut bodies = Vec::new();
489    /// while !input.is_empty() {
490    ///     let n = d.feed(input);
491    ///     input = &input[n..];
492    ///     while let Some(body) = d.next_frame()? {
493    ///         bodies.push(body.to_vec());
494    ///     }
495    /// }
496    /// assert_eq!(bodies, [b"1".to_vec(), b"2".to_vec(), b"3".to_vec()]);
497    /// # Ok::<(), rpc_io::FrameError>(())
498    /// ```
499    pub fn feed(&mut self, bytes: &[u8]) -> usize {
500        let space = self.space();
501        let n = bytes.len().min(space.len());
502        space[..n].copy_from_slice(&bytes[..n]);
503        self.commit(n);
504        n
505    }
506
507    /// The next complete message body, `Ok(None)` when more bytes are needed.
508    ///
509    /// # Errors
510    ///
511    /// A [`FrameError`]. After [`TooLarge`](FrameError::TooLarge) call again:
512    /// the decoder has moved on. Any other error is final and returned again
513    /// by every later call.
514    ///
515    /// # Examples
516    ///
517    /// ```
518    /// use rpc_io::{FrameError, Framing, Limits};
519    ///
520    /// let mut d = Framing::ContentLength.decoder(&Limits::new().with_max_message_bytes(3));
521    /// d.feed(b"Content-Length: 5\r\n\r\nhelloContent-Length: 2\r\n\r\nok");
522    /// assert_eq!(d.next_frame(), Err(FrameError::TooLarge { length: Some(5), limit: 3 }));
523    /// assert_eq!(d.next_frame(), Ok(Some(&b"ok"[..])));
524    /// ```
525    pub fn next_frame(&mut self) -> Result<Option<&[u8]>, FrameError> {
526        match self.next_range() {
527            Ok(Some(range)) => Ok(Some(&self.buf[range])),
528            Ok(None) => Ok(None),
529            Err(error) => Err(error),
530        }
531    }
532
533    /// Ends the stream: call when the input is exhausted, after
534    /// [`next_frame`](Decoder::next_frame) has returned `Ok(None)`.
535    ///
536    /// Returns a final newline-delimited message that had no `\n` (the end of
537    /// the stream ends the line), and `Ok(None)` when the stream ended
538    /// cleanly between messages. Call until it returns `Ok(None)` or an error.
539    ///
540    /// # Errors
541    ///
542    /// [`FrameError::Truncated`] if the stream ended inside a Content-Length
543    /// message (headers or body); any error `next_frame` would return.
544    ///
545    /// # Examples
546    ///
547    /// ```
548    /// use rpc_io::{FrameError, Framing, Limits};
549    ///
550    /// let mut d = Framing::Newline.decoder(&Limits::new());
551    /// d.feed(b"{\"last\":true}");
552    /// assert_eq!(d.next_frame(), Ok(None));
553    /// assert_eq!(d.finish(), Ok(Some(&b"{\"last\":true}"[..])));
554    /// assert_eq!(d.finish(), Ok(None));
555    ///
556    /// let mut d = Framing::ContentLength.decoder(&Limits::new());
557    /// d.feed(b"Content-Length: 9\r\n\r\n{}");
558    /// assert_eq!(d.next_frame(), Ok(None));
559    /// assert_eq!(d.finish(), Err(FrameError::Truncated));
560    /// ```
561    pub fn finish(&mut self) -> Result<Option<&[u8]>, FrameError> {
562        match self.finish_range() {
563            Ok(Some(range)) => Ok(Some(&self.buf[range])),
564            Ok(None) => Ok(None),
565            Err(error) => Err(error),
566        }
567    }
568
569    fn fresh(framing: Framing) -> State {
570        match framing {
571            Framing::ContentLength => State::Headers {
572                lines: 0,
573                bytes: 0,
574                length: None,
575            },
576            Framing::Newline => State::Line,
577        }
578    }
579
580    fn fail(&mut self, error: FrameError) -> FrameError {
581        self.failed = Some(error);
582        error
583    }
584
585    fn finish_range(&mut self) -> Result<Option<Range<usize>>, FrameError> {
586        if let Some(range) = self.next_range()? {
587            return Ok(Some(range));
588        }
589        let rest = self.start..self.end;
590        match self.state {
591            State::Headers { lines: 0, .. } if is_blank(&self.buf[rest.clone()]) => {
592                self.start = self.end;
593                Ok(None)
594            }
595            State::Headers { .. } | State::Body { .. } | State::Skip { .. } => {
596                Err(self.fail(FrameError::Truncated))
597            }
598            State::Line => {
599                self.start = self.end;
600                self.scan = self.end;
601                let line = trim_line(&self.buf, rest);
602                if line.len() > self.max_message {
603                    Err(self.line_too_large())
604                } else if is_blank(&self.buf[line.clone()]) {
605                    Ok(None)
606                } else {
607                    Ok(Some(line))
608                }
609            }
610            State::Discard => {
611                self.start = self.end;
612                self.scan = self.end;
613                Ok(None)
614            }
615        }
616    }
617
618    fn next_range(&mut self) -> Result<Option<Range<usize>>, FrameError> {
619        if let Some(error) = self.failed {
620            return Err(error);
621        }
622        loop {
623            match self.state {
624                State::Headers {
625                    lines,
626                    bytes,
627                    length,
628                } => {
629                    let Some(at) = find_newline(&self.buf[self.scan..self.end]) else {
630                        self.scan = self.end;
631                        let pending = self.end - self.start;
632                        if bytes.saturating_add(pending) > self.max_header_bytes {
633                            return Err(self.fail(FrameError::HeaderTooLarge {
634                                limit: self.max_header_bytes,
635                            }));
636                        }
637                        return Ok(self.wait());
638                    };
639                    let line_end = self.scan + at + 1;
640                    let line_len = line_end - self.start;
641                    let line = trim_line(&self.buf, self.start..line_end - 1);
642                    if line.is_empty() {
643                        self.start = line_end;
644                        self.scan = line_end;
645                        if lines == 0 {
646                            // Stray blank lines between messages are skipped.
647                            continue;
648                        }
649                        self.end_headers(length)?;
650                        continue;
651                    }
652                    let bytes = bytes.saturating_add(line_len);
653                    if bytes > self.max_header_bytes {
654                        return Err(self.fail(FrameError::HeaderTooLarge {
655                            limit: self.max_header_bytes,
656                        }));
657                    }
658                    let lines = lines + 1;
659                    if lines > self.max_headers {
660                        return Err(self.fail(FrameError::TooManyHeaders {
661                            limit: self.max_headers,
662                        }));
663                    }
664                    let length = match parse_header(&self.buf[line]) {
665                        Header::ContentLength(_) if length.is_some() => {
666                            return Err(self.fail(FrameError::DuplicateContentLength));
667                        }
668                        Header::ContentLength(n) => Some(n),
669                        Header::Other => length,
670                        Header::Invalid(error) => return Err(self.fail(error)),
671                    };
672                    self.start = line_end;
673                    self.scan = line_end;
674                    self.state = State::Headers {
675                        lines,
676                        bytes,
677                        length,
678                    };
679                }
680                State::Body { length } => {
681                    if self.end - self.start < length {
682                        return Ok(self.wait());
683                    }
684                    let body = self.start..self.start + length;
685                    self.start += length;
686                    self.scan = self.start;
687                    self.state = Self::fresh(self.framing);
688                    return Ok(Some(body));
689                }
690                State::Skip { remaining } => {
691                    let available = (self.end - self.start) as u64;
692                    let take = available.min(remaining);
693                    // `take` is at most `available`, a `usize`.
694                    self.start += take as usize;
695                    self.scan = self.start;
696                    if take == remaining {
697                        self.state = Self::fresh(self.framing);
698                        continue;
699                    }
700                    self.state = State::Skip {
701                        remaining: remaining - take,
702                    };
703                    return Ok(self.wait());
704                }
705                State::Line => {
706                    let Some(at) = find_newline(&self.buf[self.scan..self.end]) else {
707                        self.scan = self.end;
708                        // The line so far, plus an `\r` that may precede its end.
709                        if self.end - self.start > self.max_message.saturating_add(1) {
710                            self.start = self.end;
711                            self.scan = self.end;
712                            self.state = State::Discard;
713                            return Err(self.line_too_large());
714                        }
715                        return Ok(self.wait());
716                    };
717                    let newline = self.scan + at;
718                    let line = trim_line(&self.buf, self.start..newline);
719                    self.start = newline + 1;
720                    self.scan = self.start;
721                    // Length before blankness, and no length in the error: a
722                    // line that arrives in pieces is judged on its length
723                    // alone (above), so a whole one must be too, or the
724                    // result would depend on how the input was split.
725                    if line.len() > self.max_message {
726                        return Err(self.line_too_large());
727                    }
728                    if is_blank(&self.buf[line.clone()]) {
729                        continue;
730                    }
731                    return Ok(Some(line));
732                }
733                State::Discard => match find_newline(&self.buf[self.scan..self.end]) {
734                    Some(at) => {
735                        self.start = self.scan + at + 1;
736                        self.scan = self.start;
737                        self.state = State::Line;
738                    }
739                    None => {
740                        self.start = self.end;
741                        self.scan = self.end;
742                        return Ok(self.wait());
743                    }
744                },
745            }
746        }
747    }
748
749    /// Ends a header section: the body comes next, or is skipped when too
750    /// large.
751    fn end_headers(&mut self, length: Option<u64>) -> Result<(), FrameError> {
752        let Some(length) = length else {
753            return Err(self.fail(FrameError::MissingContentLength));
754        };
755        match usize::try_from(length) {
756            Ok(n) if n <= self.max_message => {
757                self.state = State::Body { length: n };
758                Ok(())
759            }
760            _ => {
761                self.state = State::Skip { remaining: length };
762                Err(FrameError::TooLarge {
763                    length: Some(length),
764                    limit: self.max_message,
765                })
766            }
767        }
768    }
769
770    /// The error for a newline-delimited line over the limit. Its length is
771    /// not given: a line cut off before its end has no known length, and
772    /// reporting it only when the end happened to be buffered would make the
773    /// error depend on how the input was split.
774    fn line_too_large(&self) -> FrameError {
775        FrameError::TooLarge {
776            length: None,
777            limit: self.max_message,
778        }
779    }
780
781    /// Nothing complete is buffered: more bytes may be taken.
782    fn wait<T>(&mut self) -> Option<T> {
783        self.drained = true;
784        None
785    }
786}
787
788/// One parsed header line.
789enum Header {
790    ContentLength(u64),
791    Other,
792    Invalid(FrameError),
793}
794
795fn parse_header(line: &[u8]) -> Header {
796    let Some(colon) = line.iter().position(|&b| b == b':') else {
797        return Header::Invalid(FrameError::InvalidHeader);
798    };
799    let (name, value) = line.split_at(colon);
800    // RFC 9110 field names are tokens. Anything else (a space, a brace) is a
801    // body that ran into the headers, not a header to skip over.
802    if name.is_empty() || !name.iter().all(|&b| is_token(b)) {
803        return Header::Invalid(FrameError::InvalidHeader);
804    }
805    if !name.eq_ignore_ascii_case(b"content-length") {
806        return Header::Other;
807    }
808    let value = trim_spaces(&value[1..]);
809    if value.is_empty() {
810        return Header::Invalid(FrameError::InvalidContentLength);
811    }
812    let mut n: u64 = 0;
813    for &b in value {
814        if !b.is_ascii_digit() {
815            return Header::Invalid(FrameError::InvalidContentLength);
816        }
817        let Some(next) = n
818            .checked_mul(10)
819            .and_then(|n| n.checked_add(u64::from(b - b'0')))
820        else {
821            return Header::Invalid(FrameError::InvalidContentLength);
822        };
823        n = next;
824    }
825    Header::ContentLength(n)
826}
827
828/// Whether `b` may appear in an HTTP field name (RFC 9110 `tchar`).
829fn is_token(b: u8) -> bool {
830    b.is_ascii_alphanumeric() || b"!#$%&'*+-.^_`|~".contains(&b)
831}
832
833/// `bytes` without leading and trailing spaces and tabs.
834fn trim_spaces(bytes: &[u8]) -> &[u8] {
835    let start = bytes.iter().position(|&b| b != b' ' && b != b'\t');
836    let end = bytes.iter().rposition(|&b| b != b' ' && b != b'\t');
837    match (start, end) {
838        (Some(start), Some(end)) => &bytes[start..=end],
839        _ => &[],
840    }
841}
842
843/// `range` without a trailing `\r`.
844fn trim_line(buf: &[u8], range: Range<usize>) -> Range<usize> {
845    if range.end > range.start && buf[range.end - 1] == b'\r' {
846        range.start..range.end - 1
847    } else {
848        range
849    }
850}
851
852/// Whether `bytes` holds only JSON whitespace.
853fn is_blank(bytes: &[u8]) -> bool {
854    bytes
855        .iter()
856        .all(|&b| matches!(b, b' ' | b'\t' | b'\r' | b'\n'))
857}
858
859const ONES: u64 = 0x0101_0101_0101_0101;
860const HIGHS: u64 = 0x8080_8080_8080_8080;
861
862/// Whether any byte of `word` is zero.
863#[inline]
864const fn has_zero(word: u64) -> bool {
865    word.wrapping_sub(ONES) & !word & HIGHS != 0
866}
867
868/// The first byte of `hay` that `hit` matches, eight bytes at a time where a
869/// word-wide test can rule a chunk out.
870#[inline]
871fn find_with(
872    hay: &[u8],
873    word_hit: impl Fn(u64) -> bool,
874    hit: impl Fn(u8) -> bool,
875) -> Option<usize> {
876    let mut chunks = hay.chunks_exact(8);
877    let mut base = 0;
878    for chunk in &mut chunks {
879        let word = u64::from_le_bytes([
880            chunk[0], chunk[1], chunk[2], chunk[3], chunk[4], chunk[5], chunk[6], chunk[7],
881        ]);
882        if word_hit(word) {
883            return chunk.iter().position(|&b| hit(b)).map(|i| base + i);
884        }
885        base += 8;
886    }
887    chunks
888        .remainder()
889        .iter()
890        .position(|&b| hit(b))
891        .map(|i| base + i)
892}
893
894/// The first `\n` in `hay`.
895pub(crate) fn find_newline(hay: &[u8]) -> Option<usize> {
896    find_with(
897        hay,
898        |w| has_zero(w ^ (ONES * u64::from(b'\n'))),
899        |b| b == b'\n',
900    )
901}
902
903/// The first `\n` or `\r` in `hay`.
904fn find_line_break(hay: &[u8]) -> Option<usize> {
905    find_with(
906        hay,
907        |w| has_zero(w ^ (ONES * u64::from(b'\n'))) || has_zero(w ^ (ONES * u64::from(b'\r'))),
908        |b| b == b'\n' || b == b'\r',
909    )
910}
911
912/// The decimal digits of `n`, right-aligned, and where they start.
913fn decimal(mut n: u64) -> ([u8; 20], usize) {
914    let mut digits = [0u8; 20];
915    let mut at = digits.len();
916    loop {
917        at -= 1;
918        // `n % 10` is below 10, so the cast cannot truncate.
919        digits[at] = b'0' + (n % 10) as u8;
920        n /= 10;
921        if n == 0 {
922            break;
923        }
924    }
925    (digits, at)
926}
927
928#[cfg(test)]
929#[allow(clippy::panic)]
930mod tests {
931    use alloc::vec;
932
933    use proptest::prelude::*;
934
935    use super::*;
936
937    fn frames(
938        framing: Framing,
939        limits: &Limits,
940        input: &[u8],
941        chunk: usize,
942    ) -> Vec<Result<Vec<u8>, FrameError>> {
943        let mut d = framing.decoder(limits);
944        let mut out = Vec::new();
945        let mut rest = input;
946        loop {
947            loop {
948                match d.next_frame() {
949                    Ok(Some(f)) => out.push(Ok(f.to_vec())),
950                    Ok(None) => break,
951                    Err(e) => {
952                        out.push(Err(e));
953                        if !e.is_recoverable() {
954                            return out;
955                        }
956                    }
957                }
958                assert!(d.buf.len() <= d.memory_bound());
959            }
960            if rest.is_empty() {
961                break;
962            }
963            let take = rest.len().min(chunk.max(1));
964            let n = d.feed(&rest[..take]);
965            rest = &rest[n..];
966            assert!(
967                d.buf.len() <= d.memory_bound(),
968                "{} > {}",
969                d.buf.len(),
970                d.memory_bound()
971            );
972        }
973        loop {
974            match d.finish() {
975                Ok(Some(f)) => out.push(Ok(f.to_vec())),
976                Ok(None) => break,
977                Err(e) => {
978                    out.push(Err(e));
979                    if !e.is_recoverable() {
980                        break;
981                    }
982                }
983            }
984        }
985        out
986    }
987
988    #[test]
989    fn test_content_length_basic() {
990        let input = b"\r\nContent-Length: 2\r\ncontent-type: x\r\n\r\n{}content-length:3\n\n[1]";
991        let got = frames(Framing::ContentLength, &Limits::new(), input, 3);
992        assert_eq!(got, vec![Ok(b"{}".to_vec()), Ok(b"[1]".to_vec())]);
993    }
994
995    #[test]
996    fn test_content_length_errors() {
997        let limits = Limits::new().with_max_headers(2).with_max_header_bytes(64);
998        for (input, error) in [
999            (
1000                &b"Content-Length: -1\r\n\r\n"[..],
1001                FrameError::InvalidContentLength,
1002            ),
1003            (
1004                b"Content-Length: \r\n\r\n",
1005                FrameError::InvalidContentLength,
1006            ),
1007            (
1008                b"Content-Length: 99999999999999999999\r\n\r\n",
1009                FrameError::InvalidContentLength,
1010            ),
1011            (
1012                b"Content-Length: 1 2\r\n\r\n",
1013                FrameError::InvalidContentLength,
1014            ),
1015            (
1016                b"Content-Length: +1\r\n\r\n",
1017                FrameError::InvalidContentLength,
1018            ),
1019            (b"X: 1\r\n\r\n", FrameError::MissingContentLength),
1020            (
1021                b"Content-Length: 1\r\nContent-Length: 1\r\n\r\n",
1022                FrameError::DuplicateContentLength,
1023            ),
1024            (b"nocolon\r\n\r\n", FrameError::InvalidHeader),
1025            (
1026                b"A: 1\r\nB: 2\r\nC: 3\r\n",
1027                FrameError::TooManyHeaders { limit: 2 },
1028            ),
1029            (&[b'x'; 100][..], FrameError::HeaderTooLarge { limit: 64 }),
1030            (b"Content-Length: 5\r\n\r\nab", FrameError::Truncated),
1031            (b"Content-Len", FrameError::Truncated),
1032        ] {
1033            let got = frames(Framing::ContentLength, &limits, input, 7);
1034            assert_eq!(
1035                got.last(),
1036                Some(&Err(error)),
1037                "{:?}",
1038                core::str::from_utf8(input)
1039            );
1040        }
1041    }
1042
1043    #[test]
1044    fn test_content_length_overflowing_u64_is_invalid_not_large() {
1045        let got = frames(
1046            Framing::ContentLength,
1047            &Limits::new(),
1048            b"Content-Length: 18446744073709551616\r\n\r\n",
1049            64,
1050        );
1051        assert_eq!(got, vec![Err(FrameError::InvalidContentLength)]);
1052        let got = frames(
1053            Framing::ContentLength,
1054            &Limits::new(),
1055            b"Content-Length: 18446744073709551615\r\n\r\n",
1056            64,
1057        );
1058        assert_eq!(
1059            got,
1060            vec![
1061                Err(FrameError::TooLarge {
1062                    length: Some(u64::MAX),
1063                    limit: 64 * 1024 * 1024
1064                }),
1065                Err(FrameError::Truncated)
1066            ]
1067        );
1068    }
1069
1070    #[test]
1071    fn test_oversized_body_is_skipped_without_buffering() {
1072        let limits = Limits::new().with_max_message_bytes(4);
1073        let mut input = b"Content-Length: 100000\r\n\r\n".to_vec();
1074        input.extend(core::iter::repeat_n(b'x', 100_000));
1075        input.extend_from_slice(b"Content-Length: 2\r\n\r\nok");
1076        let got = frames(Framing::ContentLength, &limits, &input, 4096);
1077        assert_eq!(
1078            got,
1079            vec![
1080                Err(FrameError::TooLarge {
1081                    length: Some(100_000),
1082                    limit: 4
1083                }),
1084                Ok(b"ok".to_vec())
1085            ]
1086        );
1087    }
1088
1089    #[test]
1090    fn test_newline_basic() {
1091        let input = b"\n  \r\n{\"a\":1}\r\n[2]\n\n3";
1092        let got = frames(Framing::Newline, &Limits::new(), input, 2);
1093        assert_eq!(
1094            got,
1095            vec![
1096                Ok(b"{\"a\":1}".to_vec()),
1097                Ok(b"[2]".to_vec()),
1098                Ok(b"3".to_vec())
1099            ]
1100        );
1101    }
1102
1103    #[test]
1104    fn test_newline_oversized_line_is_skipped() {
1105        let limits = Limits::new().with_max_message_bytes(4);
1106        let mut input = vec![b'y'; 50_000];
1107        input.extend_from_slice(b"\nok\n12345\n");
1108        let got = frames(Framing::Newline, &limits, &input, 1000);
1109        assert_eq!(
1110            got,
1111            vec![
1112                Err(FrameError::TooLarge {
1113                    length: None,
1114                    limit: 4
1115                }),
1116                Ok(b"ok".to_vec()),
1117                Err(FrameError::TooLarge {
1118                    length: None,
1119                    limit: 4
1120                }),
1121            ]
1122        );
1123    }
1124
1125    #[test]
1126    fn test_body_reserve_grows_with_arrival() {
1127        let mut d = Framing::ContentLength.decoder(&Limits::new());
1128        let _taken = d.feed(b"Content-Length: 60000000\r\n\r\n");
1129        assert_eq!(d.next_frame(), Ok(None));
1130        // The header alone does not reserve 60 MB.
1131        assert!(d.space().len() <= 2 * READ_CHUNK);
1132    }
1133
1134    #[test]
1135    fn test_encode_newline_replaces_breaks() {
1136        let mut out = Vec::new();
1137        Framing::Newline.encode(b"{\r\n\"a\":\n1}", &mut out);
1138        assert_eq!(out, b"{  \"a\": 1}\n");
1139    }
1140
1141    #[test]
1142    fn test_find_newline_matches_naive() {
1143        let mut hay = vec![b'a'; 40];
1144        assert_eq!(find_newline(&hay), None);
1145        for at in 0..40 {
1146            hay[at] = b'\n';
1147            assert_eq!(find_newline(&hay), Some(at));
1148            hay[at] = 0x8a; // high bit set, not a newline
1149            assert_eq!(find_newline(&hay), None);
1150            hay[at] = b'a';
1151        }
1152    }
1153
1154    proptest! {
1155        #[test]
1156        fn prop_chunking_does_not_change_frames(
1157            input in proptest::collection::vec(prop_oneof![Just(b'\n'), Just(b'\r'), Just(b':'), Just(b'7'), any::<u8>()], 0..600),
1158            a in 1usize..64,
1159            b in 1usize..64,
1160            newline in any::<bool>(),
1161        ) {
1162            let framing = if newline { Framing::Newline } else { Framing::ContentLength };
1163            let limits = Limits::new().with_max_message_bytes(40).with_max_header_bytes(48).with_max_headers(3);
1164            prop_assert_eq!(frames(framing, &limits, &input, a), frames(framing, &limits, &input, b));
1165        }
1166    }
1167}