granit_parser/input/
buffered.rs

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

granit_parser/input/
buffered.rs
