granit_parser/input/
buffered.rs

1use crate::char_traits::is_breakz;
2use crate::error::ErrorKind;
3use crate::input::{BorrowedInput, Input};
4
5use alloc::string::String;
6use arraydeque::ArrayDeque;
7
8/// The size of the [`BufferedInput`] buffer.
9///
10/// The buffer is statically allocated to avoid conditions for reallocations each time we
11/// consume/push a character. As of now, almost all lookaheads are 4 characters maximum, except:
12///   - Escape sequences parsing: some escape codes are 8 characters
13///   - Scanning indent in scalars: this looks ahead `indent + 2` characters
14///
15/// This constant must be set to at least 8. When scanning indent in scalars, the lookahead is done
16/// in a single call if and only if the indent is `BUFFER_LEN - 2` or less. If the indent is higher
17/// than that, the code will fall back to a loop of lookaheads.
18const BUFFER_LEN: usize = 16;
19
20/// A wrapper around an [`Iterator`] of [`char`]s with a buffer.
21///
22/// The YAML scanner often needs some lookahead. With fully allocated buffers such as `String` or
23/// `&str`, this is not an issue. However, with streams, we need to have a way of peeking multiple
24/// characters at a time and sometimes pushing some back into the stream.
25/// Doing this directly with iterator adapters would require pulling in all of `itertools` for one
26/// method, so this structure keeps the buffering local.
27#[allow(clippy::module_name_repetitions)]
28pub struct BufferedInput<T: Iterator<Item = char>> {
29    /// The iterator source.
30    input: T,
31    /// Buffer for the next characters to consume.
32    buffer: ArrayDeque<char, BUFFER_LEN>,
33    /// Number of front buffer characters that came from the iterator, not EOF padding.
34    real_buffered: usize,
35    /// Largest active lookahead window requested by the scanner.
36    lookahead: usize,
37    /// Whether the wrapped iterator has reported EOF.
38    source_exhausted: bool,
39}
40
41impl<T: Iterator<Item = char>> BufferedInput<T> {
42    /// Create a new [`BufferedInput`] over the given character iterator.
43    #[must_use]
44    pub fn new(input: T) -> Self {
45        Self {
46            input,
47            buffer: ArrayDeque::default(),
48            real_buffered: 0,
49            lookahead: 0,
50            source_exhausted: false,
51        }
52    }
53
54    fn push_source_or_padding(&mut self) {
55        let c = if self.source_exhausted {
56            '\0'
57        } else if let Some(c) = self.input.next() {
58            self.real_buffered += 1;
59            c
60        } else {
61            self.source_exhausted = true;
62            '\0'
63        };
64        self.buffer.push_back(c).unwrap();
65    }
66
67    fn fill_lookahead(&mut self) {
68        while self.buffer.len() < self.lookahead {
69            self.push_source_or_padding();
70        }
71    }
72
73    fn pop_buffered(&mut self) -> Option<(char, bool)> {
74        let c = self.buffer.pop_front()?;
75        let is_real = self.real_buffered > 0;
76        if is_real {
77            self.real_buffered -= 1;
78        }
79        Some((c, is_real))
80    }
81
82    fn read_source_or_eof(&mut self) -> (char, bool) {
83        if self.source_exhausted {
84            ('\0', false)
85        } else if let Some(c) = self.input.next() {
86            (c, true)
87        } else {
88            self.source_exhausted = true;
89            ('\0', false)
90        }
91    }
92
93    fn raw_read_front(&mut self) -> (char, bool) {
94        let read = self
95            .pop_buffered()
96            .unwrap_or_else(|| self.read_source_or_eof());
97        self.fill_lookahead();
98        read
99    }
100
101    fn skip_one(&mut self) -> bool {
102        let skipped = match self.pop_buffered() {
103            Some((_, true)) => true,
104            Some((_, false)) => {
105                self.buffer.push_front('\0').unwrap();
106                false
107            }
108            None => self.read_source_or_eof().1,
109        };
110
111        if skipped {
112            self.fill_lookahead();
113        }
114        skipped
115    }
116}
117
118impl<T: Iterator<Item = char>> Input for BufferedInput<T> {
119    #[inline]
120    fn lookahead(&mut self, count: usize) {
121        self.lookahead = self.lookahead.max(count.min(BUFFER_LEN));
122        self.fill_lookahead();
123    }
124
125    #[inline]
126    fn buflen(&self) -> usize {
127        self.lookahead
128    }
129
130    #[inline]
131    fn bufmaxlen(&self) -> usize {
132        BUFFER_LEN
133    }
134
135    #[inline]
136    fn raw_read_ch(&mut self) -> char {
137        self.raw_read_front().0
138    }
139
140    #[inline]
141    fn raw_read_non_breakz_ch(&mut self) -> Option<char> {
142        if let Some(c) = self.buffer.front().copied() {
143            if is_breakz(c) {
144                None
145            } else {
146                Some(self.raw_read_front().0)
147            }
148        } else {
149            let (c, is_real) = self.read_source_or_eof();
150            if !is_real {
151                None
152            } else if is_breakz(c) {
153                self.buffer.push_back(c).unwrap();
154                self.real_buffered += 1;
155                None
156            } else {
157                self.fill_lookahead();
158                Some(c)
159            }
160        }
161    }
162
163    fn fetch_block_scalar_line(&mut self, out: &mut String) -> usize {
164        let mut consumed = 0;
165
166        // Drain existing lookahead before reading directly from the iterator. Keep both
167        // real delimiters and EOF padding at the front of the logical stream.
168        while let Some(character) = self.buffer.front().copied() {
169            if is_breakz(character) {
170                self.fill_lookahead();
171                return consumed;
172            }
173            self.pop_buffered();
174            out.push(character);
175            consumed += 1;
176        }
177
178        if !self.source_exhausted {
179            for character in self.input.by_ref() {
180                if is_breakz(character) {
181                    self.buffer.push_back(character).unwrap();
182                    self.real_buffered += 1;
183                    self.fill_lookahead();
184                    return consumed;
185                }
186                out.push(character);
187                consumed += 1;
188            }
189            self.source_exhausted = true;
190        }
191
192        // Restore the active window once for the entire line, including at EOF. A
193        // fallible iterator's first error stays latched in its adapter during this refill.
194        self.fill_lookahead();
195        consumed
196    }
197
198    #[inline]
199    fn skip(&mut self) {
200        self.skip_one();
201    }
202
203    #[inline]
204    fn skip_n(&mut self, count: usize) {
205        for _ in 0..count {
206            if !self.skip_one() {
207                break;
208            }
209        }
210    }
211
212    #[inline]
213    fn peek(&self) -> char {
214        self.buffer.front().copied().unwrap_or('\0')
215    }
216
217    #[inline]
218    fn peek_nth(&self, n: usize) -> char {
219        self.buffer.get(n).copied().unwrap_or('\0')
220    }
221
222    #[inline]
223    fn next_is_z(&self) -> bool {
224        self.source_exhausted && self.real_buffered == 0
225    }
226}
227
228/// `BufferedInput` does not support zero-copy slicing since it's a streaming input
229/// without stable backing storage.
230impl<T: Iterator<Item = char>> BorrowedInput<'static> for BufferedInput<T> {
231    #[inline]
232    fn slice_borrowed(&self, _start: usize, _end: usize) -> Option<&'static str> {
233        None
234    }
235}
236
237/// Adapter that exposes successful items to [`BufferedInput`] and latches the first source error.
238struct FallibleChars<T: Iterator<Item = Result<char, ErrorKind>>> {
239    input: T,
240    error: Option<ErrorKind>,
241    finished: bool,
242}
243
244impl<T: Iterator<Item = Result<char, ErrorKind>>> FallibleChars<T> {
245    fn new(input: T) -> Self {
246        Self {
247            input,
248            error: None,
249            finished: false,
250        }
251    }
252}
253
254impl<T: Iterator<Item = Result<char, ErrorKind>>> Iterator for FallibleChars<T> {
255    type Item = char;
256
257    fn next(&mut self) -> Option<Self::Item> {
258        if self.finished {
259            return None;
260        }
261
262        match self.input.next() {
263            Some(Ok(c)) => Some(c),
264            Some(Err(error)) => {
265                self.error = Some(error);
266                self.finished = true;
267                None
268            }
269            None => {
270                self.finished = true;
271                None
272            }
273        }
274    }
275}
276
277/// A buffered wrapper around a fallible iterator of characters.
278///
279/// The iterator uses its normal `None` return value for clean end-of-input and returns source
280/// failures as `Some(Err(error))`, where `error` is an [`ErrorKind`]. The first error is latched,
281/// parsing becomes terminal, and the underlying iterator is never polled again.
282#[allow(clippy::module_name_repetitions)]
283pub struct FallibleBufferedInput<T: Iterator<Item = Result<char, ErrorKind>>> {
284    inner: BufferedInput<FallibleChars<T>>,
285}
286
287impl<T: Iterator<Item = Result<char, ErrorKind>>> FallibleBufferedInput<T> {
288    /// Create a buffered input over a fallible character iterator.
289    #[must_use]
290    pub fn new(input: T) -> Self {
291        Self {
292            inner: BufferedInput::new(FallibleChars::new(input)),
293        }
294    }
295}
296
297impl<T: Iterator<Item = Result<char, ErrorKind>>> Input for FallibleBufferedInput<T> {
298    #[inline]
299    fn lookahead(&mut self, count: usize) {
300        self.inner.lookahead(count);
301    }
302
303    #[inline]
304    fn buflen(&self) -> usize {
305        self.inner.buflen()
306    }
307
308    #[inline]
309    fn bufmaxlen(&self) -> usize {
310        self.inner.bufmaxlen()
311    }
312
313    #[inline]
314    fn raw_read_ch(&mut self) -> char {
315        self.inner.raw_read_ch()
316    }
317
318    #[inline]
319    fn raw_read_non_breakz_ch(&mut self) -> Option<char> {
320        self.inner.raw_read_non_breakz_ch()
321    }
322
323    #[inline]
324    fn fetch_block_scalar_line(&mut self, out: &mut String) -> usize {
325        self.inner.fetch_block_scalar_line(out)
326    }
327
328    #[inline]
329    fn skip(&mut self) {
330        self.inner.skip();
331    }
332
333    #[inline]
334    fn skip_n(&mut self, count: usize) {
335        self.inner.skip_n(count);
336    }
337
338    #[inline]
339    fn peek(&self) -> char {
340        self.inner.peek()
341    }
342
343    #[inline]
344    fn peek_nth(&self, n: usize) -> char {
345        self.inner.peek_nth(n)
346    }
347
348    #[inline]
349    fn next_is_z(&self) -> bool {
350        self.inner.next_is_z()
351    }
352
353    #[inline]
354    fn take_source_error(&mut self) -> Option<ErrorKind> {
355        self.inner.input.error.take()
356    }
357}
358
359/// `FallibleBufferedInput` is a streaming input and cannot provide stable borrowed slices.
360impl<T: Iterator<Item = Result<char, ErrorKind>>> BorrowedInput<'static>
361    for FallibleBufferedInput<T>
362{
363    #[inline]
364    fn slice_borrowed(&self, _start: usize, _end: usize) -> Option<&'static str> {
365        None
366    }
367}
368
369#[cfg(test)]
370mod tests {
371    use crate::input::str::StrInput;
372
373    use super::*;
374
375    #[test]
376    fn lookahead_larger_than_buffer_is_clamped() {
377        let mut input = BufferedInput::new("abc".chars());
378
379        input.lookahead(BUFFER_LEN + 8);
380
381        assert_eq!(input.buflen(), BUFFER_LEN);
382        assert_eq!(input.peek(), 'a');
383        assert_eq!(input.peek_nth(1), 'b');
384        assert_eq!(input.peek_nth(2), 'c');
385        assert_eq!(input.peek_nth(3), '\0');
386    }
387
388    #[test]
389    fn raw_reads_use_stream_front_and_report_eof() {
390        let mut input = BufferedInput::new("a".chars());
391
392        assert_eq!(input.raw_read_ch(), 'a');
393        assert_eq!(input.raw_read_ch(), '\0');
394
395        let mut input = BufferedInput::new("ab".chars());
396        input.lookahead(1);
397        assert_eq!(input.raw_read_ch(), 'a');
398        assert_eq!(input.peek(), 'b');
399    }
400
401    #[test]
402    fn raw_read_non_breakz_leaves_break_at_stream_front() {
403        let mut input = BufferedInput::new("a\n".chars());
404
405        assert_eq!(input.raw_read_non_breakz_ch(), Some('a'));
406        assert_eq!(input.raw_read_non_breakz_ch(), None);
407        assert_eq!(input.peek(), '\n');
408        input.lookahead(1);
409        assert_eq!(input.buflen(), 1);
410        assert_eq!(input.peek(), '\n');
411
412        let mut empty = BufferedInput::new("".chars());
413        assert_eq!(empty.raw_read_non_breakz_ch(), None);
414    }
415
416    #[test]
417    fn skip_n_consumes_stream_front_and_preserves_lookahead_window() {
418        let mut input = BufferedInput::new("abcdef".chars());
419
420        input.lookahead(5);
421        input.skip_n(2);
422
423        assert_eq!(input.buflen(), 5);
424        assert_eq!(input.peek(), 'c');
425        assert_eq!(input.peek_nth(3), 'f');
426        assert_eq!(input.peek_nth(4), '\0');
427    }
428
429    #[test]
430    fn skip_without_lookahead_consumes_like_str_input() {
431        let mut buffered = BufferedInput::new("ab".chars());
432        buffered.skip();
433        buffered.lookahead(1);
434
435        let mut str_input = StrInput::new("ab");
436        str_input.skip();
437        str_input.lookahead(1);
438
439        assert_eq!(buffered.peek(), str_input.peek());
440    }
441
442    #[test]
443    fn skip_n_saturates_at_eof_like_str_input() {
444        let mut buffered = BufferedInput::new("abc".chars());
445        buffered.lookahead(1);
446        buffered.skip_n(8);
447        buffered.lookahead(1);
448
449        let mut str_input = StrInput::new("abc");
450        str_input.lookahead(1);
451        str_input.skip_n(8);
452        str_input.lookahead(1);
453
454        assert_eq!(buffered.peek(), str_input.peek());
455    }
456
457    #[test]
458    fn buflen_matches_str_input_lookahead_window_after_consumption() {
459        let mut buffered = BufferedInput::new("ab".chars());
460        buffered.lookahead(2);
461        buffered.skip();
462        buffered.skip();
463
464        let mut str_input = StrInput::new("ab");
465        str_input.lookahead(2);
466        str_input.skip();
467        str_input.skip();
468
469        assert_eq!(buffered.buflen(), str_input.buflen());
470        assert_eq!(buffered.buf_is_empty(), str_input.buf_is_empty());
471        assert_eq!(buffered.peek(), str_input.peek());
472    }
473
474    #[test]
475    fn streaming_input_never_borrows_slices() {
476        let input = BufferedInput::new("abc".chars());
477
478        assert_eq!(BorrowedInput::slice_borrowed(&input, 0, 1), None);
479    }
480}
granit_parser/input/buffered.rs

granit_parser/input/
buffered.rs
