ca_formats/
macrocell.rs

1//! A parser for [Macrocell](http://golly.sourceforge.net/Help/formats.html#mc) format.
2
3use crate::Input;
4use displaydoc::Display;
5use lazy_regex::regex;
6use std::io::{BufReader, Error as IoError, Read};
7use thiserror::Error;
8
9/// Errors that can be returned when parsing a Macrocell file.
10#[derive(Debug, Error, Display)]
11pub enum Error {
12    /// Invalid header line: {0}.
13    InvalidHeaderLine(String),
14    /// Invalid node line: {0}.
15    InvalidNodeLine(String),
16    /// Error when reading from input: {0}.
17    IoError(#[from] IoError),
18}
19
20/// A node in [HashLife](https://conwaylife.com/wiki/HashLife)'s quadtree.
21#[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)]
22pub struct Node {
23    pub id: usize,
24    pub data: NodeData,
25}
26
27/// Data in a `Node`.
28#[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)]
29pub enum NodeData {
30    /// A level 1 leaf, representing a 2x2 square, in rules with more than 2 states.
31    ///
32    /// The data contains the states of four cells in the square.
33    Level1 { nw: u8, ne: u8, sw: u8, se: u8 },
34    /// A level 3 leaf, representing a 8x8 square, in rules with 2 states.
35    ///
36    /// The data is represented by a 64-bit integer.
37    Level3(u64),
38    /// A non-leaf node.
39    ///
40    /// The data contains the level of the node,
41    /// and the ids of four children.
42    Node {
43        level: u8,
44        nw: usize,
45        ne: usize,
46        sw: usize,
47        se: usize,
48    },
49}
50
51impl NodeData {
52    pub const fn level(&self) -> u8 {
53        match self {
54            Self::Level1 { .. } => 1,
55            Self::Level3(_) => 3,
56            Self::Node { level, .. } => *level,
57        }
58    }
59}
60
61/// Parse a level 3 leaf.
62fn parse_level3(line: &str) -> Option<NodeData> {
63    let mut node = 0;
64    let (mut x, mut y) = (0_u8, 0_u8);
65    for char in line.bytes() {
66        match char {
67            b'.' => x += 1,
68            b'*' => {
69                if x >= 8 || y >= 8 {
70                    return None;
71                }
72                node |= 1 << ((7 - y) * 8 + (7 - x));
73                x += 1;
74            }
75            b'$' => {
76                x = 0;
77                y += 1;
78            }
79            c if c.is_ascii_whitespace() => (),
80            _ => return None,
81        }
82    }
83    Some(NodeData::Level3(node))
84}
85
86/// Parse a level 1 leaf.
87fn parse_level1(line: &str) -> Option<NodeData> {
88    let re = regex!(r"^1\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)");
89    let cap = re.captures(line)?;
90    let nw = cap[1].parse().ok()?;
91    let ne = cap[2].parse().ok()?;
92    let sw = cap[3].parse().ok()?;
93    let se = cap[4].parse().ok()?;
94    Some(NodeData::Level1 { nw, ne, sw, se })
95}
96
97/// Parse a non-leaf node.
98fn parse_node(line: &str) -> Option<NodeData> {
99    let re = regex!(r"^(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)");
100    let cap = re.captures(line)?;
101    let level = cap[1].parse().ok()?;
102    let nw = cap[2].parse().ok()?;
103    let ne = cap[3].parse().ok()?;
104    let sw = cap[4].parse().ok()?;
105    let se = cap[5].parse().ok()?;
106    Some(NodeData::Node {
107        level,
108        nw,
109        ne,
110        sw,
111        se,
112    })
113}
114
115/// Parse the rulestring.
116fn parse_rule(line: &str) -> Option<String> {
117    let re = regex!(r"^#R\s*(?P<rule>.*\S)\s*$");
118    let cap = re.captures(line)?;
119    let rule = cap["rule"].to_string();
120    Some(rule)
121}
122
123/// Parse the current generation.
124fn parse_gen(line: &str) -> Option<u64> {
125    let re = regex!(r"^#G\s*(?P<gen>\d+)\s*$");
126    let cap = re.captures(line)?;
127    let gen = cap["gen"].parse().ok()?;
128    Some(gen)
129}
130
131/// A parser for [Macrocell](http://golly.sourceforge.net/Help/formats.html#mc) format.
132///
133/// This format is specifically designed for the [HashLife](https://conwaylife.com/wiki/HashLife)
134/// algorithm. So as an iterator, it iterates over the nodes in the quadtree,
135/// instead of the living cells.
136///
137/// # Examples
138///
139/// ## Reading from a string:
140///
141/// ```rust
142/// use ca_formats::macrocell::{Macrocell, NodeData};
143///
144/// const GLIDER: &str = r"[M2] (golly 3.4)
145/// #R B3/S23
146/// $$$$$$*$.*$
147/// .......*$
148/// **$
149/// 4 0 1 2 3";
150///
151/// let glider = Macrocell::new(GLIDER).unwrap();
152/// assert_eq!(glider.rule().unwrap(), "B3/S23");
153///
154/// let last_node = glider.last().unwrap().unwrap();
155/// assert_eq!(last_node.id, 4);
156/// assert_eq!(
157///     last_node.data,
158///     NodeData::Node {
159///         level: 4,
160///         nw: 0,
161///         ne: 1,
162///         sw: 2,
163///         se: 3,
164///     }
165/// );
166/// ```
167///
168/// ## Reading from a file:
169///
170/// ``` rust
171/// use std::fs::File;
172/// use ca_formats::macrocell::Macrocell;
173///
174/// let file = File::open("tests/sirrobin.mc").unwrap();
175/// let sirrobin = Macrocell::new_from_file(file).unwrap();
176///
177/// assert_eq!(sirrobin.count(), 42); // The number of nodes.
178#[must_use]
179#[derive(Debug)]
180pub struct Macrocell<I: Input> {
181    /// Rulestring.
182    rule: Option<String>,
183    /// Current generation.
184    gen: Option<u64>,
185    /// An iterator over lines of the Macrocell string.
186    lines: I::Lines,
187    /// The current line.
188    current_line: Option<I::Line>,
189    /// The current node id.
190    id: usize,
191}
192
193impl<I: Input> Macrocell<I> {
194    /// Create a new parser instance from input, and try to read the header lines.
195    pub fn new(input: I) -> Result<Self, Error> {
196        let mut lines = input.lines();
197        let mut rule = None;
198        let mut gen = None;
199        let mut current_line = None;
200        for item in &mut lines {
201            let line = I::line(item)?;
202            if line.as_ref().starts_with("[M2]") {
203                continue;
204            } else if line.as_ref().starts_with("#R") {
205                rule.replace(
206                    parse_rule(line.as_ref())
207                        .ok_or_else(|| Error::InvalidHeaderLine(line.as_ref().to_string()))?,
208                );
209            } else if line.as_ref().starts_with("#G") {
210                gen.replace(
211                    parse_gen(line.as_ref())
212                        .ok_or_else(|| Error::InvalidHeaderLine(line.as_ref().to_string()))?,
213                );
214            } else if !line.as_ref().starts_with('#') {
215                current_line = Some(line);
216                break;
217            }
218        }
219        Ok(Self {
220            rule,
221            gen,
222            lines,
223            current_line,
224            id: 1,
225        })
226    }
227
228    /// The rulestring.
229    pub fn rule(&self) -> Option<&str> {
230        self.rule.as_deref()
231    }
232
233    /// The current generation.
234    pub const fn gen(&self) -> Option<u64> {
235        self.gen
236    }
237}
238
239impl<I, L> Macrocell<I>
240where
241    I: Input<Lines = L>,
242    L: Input,
243{
244    /// Parse the remaining unparsed lines as a new Macrocell.
245    pub fn remains(self) -> Result<Macrocell<L>, Error> {
246        Macrocell::new(self.lines)
247    }
248}
249
250impl<R: Read> Macrocell<BufReader<R>> {
251    /// Creates a new parser instance from something that implements [`Read`] trait, e.g., a [`File`](std::fs::File).
252    pub fn new_from_file(file: R) -> Result<Self, Error> {
253        Self::new(BufReader::new(file))
254    }
255}
256
257impl<I: Input> Clone for Macrocell<I>
258where
259    I::Lines: Clone,
260    I::Line: Clone,
261{
262    fn clone(&self) -> Self {
263        Self {
264            rule: self.rule.clone(),
265            gen: self.gen,
266            lines: self.lines.clone(),
267            current_line: self.current_line.clone(),
268            id: self.id,
269        }
270    }
271}
272
273/// An iterator over quadtree nodes in an Macrocell file.
274impl<I: Input> Iterator for Macrocell<I> {
275    type Item = Result<Node, Error>;
276
277    fn next(&mut self) -> Option<Self::Item> {
278        loop {
279            if let Some(line) = self.current_line.take() {
280                if line.as_ref().starts_with('#') {
281                    continue;
282                } else if line.as_ref().starts_with(&['.', '*', '$'][..]) {
283                    if let Some(data) = parse_level3(line.as_ref()) {
284                        let node = Node { id: self.id, data };
285                        self.id += 1;
286                        return Some(Ok(node));
287                    } else {
288                        return Some(Err(Error::InvalidNodeLine(line.as_ref().to_string())));
289                    }
290                } else if line.as_ref().starts_with("1 ") {
291                    if let Some(data) = parse_level1(line.as_ref()) {
292                        let node = Node { id: self.id, data };
293                        self.id += 1;
294                        return Some(Ok(node));
295                    } else {
296                        return Some(Err(Error::InvalidNodeLine(line.as_ref().to_string())));
297                    }
298                } else if let Some(data) = parse_node(line.as_ref()) {
299                    let node = Node { id: self.id, data };
300                    self.id += 1;
301                    return Some(Ok(node));
302                } else {
303                    return Some(Err(Error::InvalidNodeLine(line.as_ref().to_string())));
304                }
305            } else if let Some(item) = self.lines.next() {
306                match I::line(item) {
307                    Ok(line) => {
308                        self.current_line = Some(line);
309                    }
310                    Err(e) => {
311                        return Some(Err(Error::IoError(e)));
312                    }
313                }
314            } else {
315                return None;
316            }
317        }
318    }
319}
320
321#[allow(clippy::unusual_byte_groupings)]
322#[cfg(test)]
323mod tests {
324    use super::*;
325
326    #[test]
327    fn macrocell_parse_line() {
328        assert_eq!(
329            parse_level3("$$..*$...*$.***$$$$"),
330            Some(NodeData::Level3(
331                0b_00000000_00000000_00100000_00010000_01110000_00000000_00000000_00000000
332            ))
333        );
334        assert_eq!(parse_level3("$$..*$...*$.***$$$$*"), None);
335        assert_eq!(
336            parse_level1("1 2 3 4 255"),
337            Some(NodeData::Level1 {
338                nw: 2,
339                ne: 3,
340                sw: 4,
341                se: 255,
342            })
343        );
344        assert_eq!(parse_level1("1 2 3 4 256"), None);
345        assert_eq!(
346            parse_node("10 20 30 40 50"),
347            Some(NodeData::Node {
348                level: 10,
349                nw: 20,
350                ne: 30,
351                sw: 40,
352                se: 50,
353            })
354        );
355        assert_eq!(parse_node("10 20 30 40"), None);
356    }
357
358    #[test]
359    fn macrocell_glider() -> Result<(), Error> {
360        const GLIDER: &str = r"[M2] (golly 3.4)
361#R B3/S23
362$$$$$$*$.*$
363.......*$
364**$
3654 0 1 2 3";
366
367        let glider = Macrocell::new(GLIDER)?;
368
369        let _ = glider.clone();
370
371        assert_eq!(glider.rule(), Some("B3/S23"));
372
373        let nodes = glider.collect::<Result<Vec<_>, _>>()?;
374        assert_eq!(
375            nodes,
376            vec![
377                Node {
378                    id: 1,
379                    data: NodeData::Level3(
380                        0b_00000000_00000000_00000000_00000000_00000000_00000000_10000000_01000000
381                    )
382                },
383                Node {
384                    id: 2,
385                    data: NodeData::Level3(
386                        0b_00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000
387                    )
388                },
389                Node {
390                    id: 3,
391                    data: NodeData::Level3(
392                        0b_11000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000
393                    )
394                },
395                Node {
396                    id: 4,
397                    data: NodeData::Node {
398                        level: 4,
399                        nw: 0,
400                        ne: 1,
401                        sw: 2,
402                        se: 3,
403                    }
404                }
405            ]
406        );
407        Ok(())
408    }
409}
ca_formats/macrocell.rs

ca_formats/
macrocell.rs
