utils/
grid.rs

1//! Grid helpers.
2
3use crate::input::InputError;
4use std::error::Error;
5use std::hint::cold_path;
6
7/// A parsed grid: `(number of rows, number of columns, data)`.
8pub type Grid<T> = (usize, usize, Vec<T>);
9
10/// Parse a 2D grid.
11///
12/// This function assumes that each byte represents one item in the grid.
13/// Using 1 byte wide output types is recommended to enable more efficient vectorization.
14///
15/// Parsing is done in two passes per line:
16///
17/// 1. A "hot" pass, where each byte is mapped to an output value and checked for validity.
18///    This uses the `hot_map` and `hot_valid` functions, which should be pure and total mappings
19///    from [`u8`] to their respective outputs to enable vectorization.
20///    Additionally, `hot_valid` must return false for both `'\r'` and `'\n'`.
21///
22/// 2. A "slow" pass, where any invalid bytes from the first pass are re-processed with their index
23///    in the final grid.
24///    This uses the `slow_map` function which returns a [`Result`], containing either a mapped
25///    value or an error.
26///    `slow_map` can be used to perform more complex, non-pure, mappings such as storing positions
27///    and will never be called for newlines or bytes that were valid in the first pass.
28///    If all the bytes were valid in the first pass, this pass is skipped.
29///
30/// `default_value` is used to initialize the grid before parsing and for any padding.
31/// A value with an all-zero bit pattern will usually faster to initialize and is recommended when
32/// padding is not used.
33///
34/// Returns (number of rows, number of columns, data) on success.
35///
36/// # Examples
37///
38/// ```
39/// # use utils::grid;
40/// assert_eq!(
41///     grid::parse(
42///         /* input         */ "##.#\n#..#\n#.##",
43///         /* padding       */ 0,
44///         /* default_value */ false,
45///         /* hot_map       */ |b| b == b'#',
46///         /* hot_valid     */ |b| matches!(b, b'.' | b'#'),
47///         /* slow_map      */ |_, _| Err("expected '.' or '#'"),
48///     ).unwrap(),
49///     (3, 4, vec![
50///         true, true, false, true,
51///         true, false, false, true,
52///         true, false, true, true,
53///     ]),
54/// );
55/// ```
56///
57///
58/// ```
59/// # use utils::grid;
60/// assert_eq!(
61///     grid::parse(
62///         /* input         */"##.#\n#..#\n#.##",
63///         /* padding       */ 2,
64///         /* default_value */ false,
65///         /* hot_map       */ |b| b == b'#',
66///         /* hot_valid     */ |b| matches!(b, b'.' | b'#'),
67///         /* slow_map      */ |_, _| Err("expected '.' or '#'"),
68///     ).unwrap(),
69///     (7, 8, vec![
70///         false, false, false, false, false, false, false, false,
71///         false, false, false, false, false, false, false, false,
72///         false, false, true, true, false, true, false, false,
73///         false, false, true, false, false, true, false, false,
74///         false, false, true, false, true, true, false, false,
75///         false, false, false, false, false, false, false, false,
76///         false, false, false, false, false, false, false, false,
77///     ]),
78/// );
79/// ```
80///
81/// ```
82/// # use utils::grid;
83/// let mut start = None;
84/// assert_eq!(
85///     grid::parse(
86///         /* input         */ ".0.#S\r\n..1..\r\n.###2\r\n.3...",
87///         /* padding       */ 1,
88///         /* default_value */ b'#',
89///         /* hot_map       */ |b| b,
90///         /* hot_valid     */ |b| matches!(b, b'.' | b'#' | b'0'..=b'9'),
91///         /* slow_map      */ |i, b| {
92///             match b {
93///                 b'S' if start.is_none() => {
94///                     start = Some(i);
95///                     Ok(b'.')
96///                 },
97///                 b'S' => Err("expected only one 'S'"),
98///                 _ => Err("expected '.', '#', 'S' or a digit")
99///             }
100///         },
101///     ).unwrap(),
102///     (6, 7, vec![
103///         b'#', b'#', b'#', b'#', b'#', b'#', b'#',
104///         b'#', b'.', b'0', b'.', b'#', b'.', b'#',
105///         b'#', b'.', b'.', b'1', b'.', b'.', b'#',
106///         b'#', b'.', b'#', b'#', b'#', b'2', b'#',
107///         b'#', b'.', b'3', b'.', b'.', b'.', b'#',
108///         b'#', b'#', b'#', b'#', b'#', b'#', b'#',
109///     ]),
110/// );
111/// assert_eq!(start, Some(12));
112/// ```
113#[inline]
114pub fn parse<T: Clone, E: Into<Box<dyn Error>>>(
115    input: &str,
116    padding: usize,
117    default_value: T,
118    hot_map: impl Fn(u8) -> T,
119    hot_valid: impl Fn(u8) -> bool,
120    mut slow_map: impl FnMut(usize, u8) -> Result<T, E>,
121) -> Result<Grid<T>, InputError> {
122    assert!(!hot_valid(b'\n'));
123    assert!(!hot_valid(b'\r'));
124    let g = parse_grid_shape(input)?;
125    let padded_cols = g.cols + 2 * padding;
126    let padded_rows = g.rows + 2 * padding;
127
128    let mut data = vec![default_value; padded_cols * padded_rows];
129    for ((r, input_line), data_line) in input
130        .as_bytes()
131        .chunks(g.line_length)
132        .enumerate()
133        .zip(data.chunks_exact_mut(padded_cols).skip(padding))
134    {
135        // Hot pass
136        let mut valid = true;
137        for (&b, d) in input_line[..g.cols]
138            .iter()
139            .zip(data_line[padding..].iter_mut())
140        {
141            *d = hot_map(b);
142            valid &= hot_valid(b);
143        }
144
145        // Slow pass
146        if !valid {
147            for ((c, &b), d) in input_line[..g.cols]
148                .iter()
149                .enumerate()
150                .zip(data_line[padding..].iter_mut())
151            {
152                if hot_valid(b) {
153                    continue;
154                }
155                if b == b'\n' || b == b'\r' {
156                    return Err(InputError::new(
157                        input,
158                        &input_line[c..],
159                        format!("expected {} columns", g.cols),
160                    ));
161                }
162
163                let index = (r + padding) * padded_cols + padding + c;
164                match slow_map(index, b) {
165                    Ok(v) => *d = v,
166                    Err(err) => return Err(InputError::new(input, &input_line[c..], err)),
167                }
168            }
169        }
170
171        // Check input_line ends in the expected newline.
172        // Do this after the slow pass, so any earlier newlines earlier in the chunk have already
173        // been caught.
174        check_newline(input, &g, r, input_line)?;
175    }
176
177    Ok((padded_rows, padded_cols, data))
178}
179
180#[derive(Clone, Copy)]
181struct GridShape {
182    cols: usize,
183    rows: usize,
184    line_length: usize,
185    crlf_endings: bool,
186}
187
188#[inline]
189fn parse_grid_shape(input: &str) -> Result<GridShape, InputError> {
190    let Some(line_length) = input
191        .bytes()
192        .position(|b| b == b'\n')
193        .map(|x| x + 1)
194        .filter(|&x| x >= 2)
195    else {
196        return Err(InputError::new(input, 0, "expected grid"));
197    };
198
199    let crlf_endings = input.as_bytes()[line_length - 2] == b'\r';
200    let newline_length = 1 + usize::from(crlf_endings);
201    if !(input.len() + newline_length).is_multiple_of(line_length) {
202        return Err(InputError::new(
203            input,
204            input.len(),
205            "expected input length to be a multiple of the first line length",
206        ));
207    }
208
209    Ok(GridShape {
210        cols: line_length - newline_length,
211        rows: (input.len() + newline_length) / line_length,
212        line_length,
213        crlf_endings,
214    })
215}
216
217#[inline]
218fn check_newline(
219    input: &str,
220    parsed_grid: &GridShape,
221    row: usize,
222    row_input: &[u8],
223) -> Result<(), InputError> {
224    if row != parsed_grid.rows - 1
225        && if parsed_grid.crlf_endings {
226            row_input.last_chunk() != Some(b"\r\n")
227        } else {
228            row_input.last_chunk() != Some(b"\n")
229        }
230    {
231        cold_path();
232        return Err(InputError::new(
233            input,
234            &row_input[row_input.len() - 2..],
235            "expected newline",
236        ));
237    }
238    Ok(())
239}
240
241/// Iterate over each row of a 2D grid and pass it to a callback after validation.
242///
243/// Unlike [`parse`], this does not support padding or allocate a transformed grid. The callback
244/// receives the row index, column count and row input bytes. The callback may be called with one
245/// or more rows before an error is found in a later row.
246///
247/// # Examples
248///
249/// ```
250/// # use utils::{grid, input::InputError};
251/// let mut row_masks = Vec::new();
252/// let input = "#.#.#\n.#.#.\n#####";
253/// let shape = grid::for_each_row(
254///     input,
255///     |b| matches!(b, b'.' | b'#'),
256///     || "expected '.' or '#'",
257///     |row, cols, row_bytes| {
258///         if row == 0 && cols > 32 {
259///             return Err(InputError::new(input, 0, "expected at most 32 columns"));
260///         }
261///         let mut bits = 0u32;
262///         for (col, &b) in row_bytes.iter().enumerate() {
263///             bits |= u32::from(b == b'#') << col;
264///         }
265///         row_masks.push(bits);
266///         Ok(())
267///     },
268/// ).unwrap();
269/// assert_eq!(shape, (3, 5));
270/// assert_eq!(row_masks, vec![0b10101, 0b01010, 0b11111]);
271/// ```
272#[inline]
273pub fn for_each_row<E: Into<Box<dyn Error>>>(
274    input: &str,
275    hot_valid: impl Fn(u8) -> bool,
276    invalid_error: impl Fn() -> E,
277    mut callback: impl FnMut(usize, usize, &[u8]) -> Result<(), InputError>,
278) -> Result<(usize, usize), InputError> {
279    assert!(!hot_valid(b'\n'));
280    assert!(!hot_valid(b'\r'));
281    let g = parse_grid_shape(input)?;
282
283    for (r, input_line) in input.as_bytes().chunks(g.line_length).enumerate() {
284        let mut all_valid = true;
285        for &b in &input_line[..g.cols] {
286            all_valid &= hot_valid(b);
287        }
288
289        if !all_valid {
290            cold_path();
291            for (c, &b) in input_line[..g.cols].iter().enumerate() {
292                if !hot_valid(b) {
293                    return Err(InputError::new(input, &input_line[c..], invalid_error()));
294                }
295            }
296            unreachable!();
297        }
298
299        check_newline(input, &g, r, input_line)?;
300
301        callback(r, g.cols, &input_line[..g.cols])?;
302    }
303
304    Ok((g.rows, g.cols))
305}
306
307/// Parse a "standard" maze with open tiles `.`, walls `#` and one start `S` and one end `E`.
308///
309/// Returns ((number of rows, number of columns, data), start index, end index) on success.
310///
311/// # Examples
312/// ```
313/// # use utils::grid;
314/// assert_eq!(
315///     grid::parse_maze("...#S\n.#E#.\n.###.\n.....", 1).unwrap(),
316///     (
317///         (6, 7, vec![
318///             b'#', b'#', b'#', b'#', b'#', b'#', b'#',
319///             b'#', b'.', b'.', b'.', b'#', b'.', b'#',
320///             b'#', b'.', b'#', b'.', b'#', b'.', b'#',
321///             b'#', b'.', b'#', b'#', b'#', b'.', b'#',
322///             b'#', b'.', b'.', b'.', b'.', b'.', b'#',
323///             b'#', b'#', b'#', b'#', b'#', b'#', b'#',
324///         ]),
325///         12,
326///         17,
327///     )
328/// );
329/// ```
330#[inline]
331pub fn parse_maze(input: &str, padding: usize) -> Result<(Grid<u8>, usize, usize), InputError> {
332    let mut start = None;
333    let mut end = None;
334    let grid = parse(
335        input,
336        padding,
337        if padding > 0 { b'#' } else { 0 },
338        |b| b,
339        |b| matches!(b, b'.' | b'#'),
340        |i, b| {
341            match b {
342                b'S' if start.is_none() => start = Some(i),
343                b'S' => return Err("expected one 'S'"),
344                b'E' if end.is_none() => end = Some(i),
345                b'E' => return Err("expected one 'E'"),
346                _ => return Err("expected '.', '#', 'S' or 'E'"),
347            }
348            Ok(b'.')
349        },
350    )?;
351    let Some(start) = start else {
352        return Err(InputError::new(input, 0, "expected one 'S'"));
353    };
354    let Some(end) = end else {
355        return Err(InputError::new(input, 0, "expected one 'E'"));
356    };
357    Ok((grid, start, end))
358}
359
360/// Checks that the provided grid has walls on each edge.
361///
362/// # Examples
363/// ```
364/// # use utils::grid::is_enclosed;
365/// assert_eq!(
366///     is_enclosed(5, 6, &[
367///         b'#', b'#', b'#', b'#', b'#', b'#',
368///         b'#', b'.', b'.', b'.', b'.', b'#',
369///         b'#', b'.', b'.', b'.', b'.', b'#',
370///         b'#', b'.', b'.', b'.', b'.', b'#',
371///         b'#', b'#', b'#', b'#', b'#', b'#',
372///     ], |&b| b == b'#'),
373///     true,
374/// );
375/// assert_eq!(
376///     is_enclosed(5, 6, &[
377///         b'#', b'#', b'#', b'#', b'#', b'#',
378///         b'#', b'.', b'.', b'.', b'.', b'#',
379///         b'#', b'.', b'.', b'.', b'.', b'#',
380///         b'#', b'.', b'.', b'.', b'.', b'.',
381///         b'#', b'#', b'#', b'#', b'#', b'#',
382///     ], |&b| b == b'#'),
383///     false,
384/// );
385/// ```
386pub fn is_enclosed<T>(rows: usize, cols: usize, grid: &[T], is_wall: impl Fn(&T) -> bool) -> bool {
387    grid[..cols].iter().all(&is_wall)
388        && grid[(rows - 1) * cols..].iter().all(&is_wall)
389        && (1..rows).all(|r| is_wall(&grid[r * cols]) && is_wall(&grid[(r + 1) * cols - 1]))
390}
utils/grid.rs

utils/
grid.rs
