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

granit_parser/input/
buffered.rs
