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