ca_formats/
rle.rs

1//! A parser for Golly's [Extended RLE format](http://golly.sourceforge.net/Help/formats.html#rle).
2//!
3//! It is basically the same as the original [RLE](https://www.conwaylife.com/wiki/Run_Length_Encoded)
4//! format, except that it supports up to 256 states, and a `#CXRLE` line.
5
6use crate::{CellData, Coordinates, Input};
7use lazy_regex::regex;
8use std::io::{BufReader, Error as IoError, Read};
9use thiserror::Error;
10
11/// Errors that can be returned when parsing a RLE file.
12#[derive(Debug, Error)]
13pub enum Error {
14    #[error("Invalid state: {0}.")]
15    InvalidState(String),
16    #[error("Invalid \"#CXRLE\" line: {0}.")]
17    InvalidCxrleLine(String),
18    #[error("Invalid header line: {0}.")]
19    InvalidHeaderLine(String),
20    #[error("Error when reading from input: {0}.")]
21    IoError(#[from] IoError),
22}
23
24/// Data from the `#CXRLE` line, e.g., `#CXRLE Pos=0,-1377 Gen=3480106827776`.
25#[derive(Clone, Debug, Eq, PartialEq, Default, Hash)]
26pub struct CxrleData {
27    /// Coordinates of the upper left corner of the pattern.
28    pub pos: Option<Coordinates>,
29    /// Current generation.
30    pub gen: Option<u64>,
31}
32
33/// Parse the `#CXRLE` line.
34fn parse_cxrle(line: &str) -> Option<CxrleData> {
35    let re = regex!(r"(?:Pos\s*=\s*(?P<x>-?\d+),\s*(?P<y>-?\d+))|(?:Gen\s*=\s*(?P<gen>\d+))");
36    let mut data = CxrleData::default();
37    for cap in re.captures_iter(line) {
38        if let Some(gen) = cap.name("gen") {
39            data.gen = Some(gen.as_str().parse().ok())?;
40        } else {
41            let x = cap["x"].parse().ok()?;
42            let y = cap["y"].parse().ok()?;
43            data.pos = Some((x, y));
44        }
45    }
46    Some(data)
47}
48
49/// Data from the header line, e.g., `x = 3, y = 3, rule = B3/S23`.
50#[derive(Clone, Debug, Eq, PartialEq, Default, Hash)]
51pub struct HeaderData {
52    /// Width of the pattern.
53    pub x: u64,
54    /// Height of the pattern.
55    pub y: u64,
56    /// Rulestring.
57    pub rule: Option<String>,
58}
59
60/// Parse the header line.
61fn parse_header(line: &str) -> Option<HeaderData> {
62    let re =
63        regex!(r"^x\s*=\s*(?P<x>\d+),\s*y\s*=\s*(?P<y>\d+)(?:,\s*rule\s*=\s*(?P<rule>.*\S)\s*)?$");
64    let mut data = HeaderData::default();
65    let cap = re.captures(line)?;
66    data.x = cap["x"].parse().ok()?;
67    data.y = cap["y"].parse().ok()?;
68    if let Some(rule) = cap.name("rule") {
69        data.rule = Some(rule.as_str().to_owned());
70    }
71    Some(data)
72}
73
74/// A parser for Golly's [Extended RLE format](http://golly.sourceforge.net/Help/formats.html#rle).
75///
76/// The format is basically the same as the original [RLE](https://www.conwaylife.com/wiki/Run_Length_Encoded)
77/// format, except that it supports up to 256 states, and a `#CXRLE` line.
78///
79/// As an iterator, it iterates over the living cells.
80///
81/// # Examples
82///
83/// ## Reading from a string:
84///
85/// ```rust
86/// use ca_formats::rle::Rle;
87///
88/// const GLIDER: &str = r"#N Glider
89/// #O Richard K. Guy
90/// #C The smallest, most common, and first discovered spaceship. Diagonal, has period 4 and speed c/4.
91/// #C www.conwaylife.com/wiki/index.php?title=Glider
92/// x = 3, y = 3, rule = B3/S23
93/// bob$2bo$3o!";
94///
95/// let glider = Rle::new(GLIDER).unwrap();
96/// assert_eq!(glider.header_data().unwrap().x, 3);
97/// assert_eq!(glider.header_data().unwrap().y, 3);
98/// assert_eq!(glider.header_data().unwrap().rule, Some(String::from("B3/S23")));
99///
100/// let cells = glider.map(|cell| cell.unwrap().position).collect::<Vec<_>>();
101/// assert_eq!(cells, vec![(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)]);
102/// ```
103///
104/// ## Reading from a file:
105///
106/// ``` rust
107/// use std::fs::File;
108/// use ca_formats::rle::Rle;
109///
110/// let file = File::open("tests/sirrobin.rle").unwrap();
111/// let sirrobin = Rle::new_from_file(file).unwrap();
112///
113/// assert_eq!(sirrobin.count(), 282);
114/// ```
115#[must_use]
116#[derive(Debug)]
117pub struct Rle<I: Input> {
118    /// Data from the `#CXRLE` line.
119    cxrle_data: Option<CxrleData>,
120
121    /// Data from the header line.
122    header_data: Option<HeaderData>,
123
124    /// An iterator over lines of the RLE string.
125    lines: I::Lines,
126
127    /// An iterator over bytes of the current line.
128    current_line: Option<I::Bytes>,
129
130    /// Coordinates of the current cell.
131    position: Coordinates,
132
133    /// X coordinates of the upper left corner of the pattern.
134    x_start: i64,
135
136    /// Run count in the RLE string, i.e., the numbers before `b`, `o`, `$` and other tags.
137    run_count: i64,
138
139    /// Remaining run count for the current cell when iterating over cells.
140    alive_count: i64,
141
142    /// State of the current cell.
143    state: u8,
144
145    /// Prefix in a multi-char state, i.e., `p` in `pA`.
146    state_prefix: Option<u8>,
147
148    /// Whether this RLE file allows unknown cells.
149    #[cfg(feature = "unknown")]
150    unknown: bool,
151}
152
153impl<I: Input> Rle<I> {
154    /// Create a new parser instance from input, and try to read the header and the `#CXRLE` line.
155    ///
156    /// If there are multiple header lines / `CXRLE` lines, only the last one will be taken.
157    pub fn new(input: I) -> Result<Self, Error> {
158        let mut lines = input.lines();
159        let mut cxrle_data = None;
160        let mut header_data = None;
161        let mut current_line = None;
162        let mut position = (0, 0);
163        let mut x_start = 0;
164        for item in &mut lines {
165            let line = I::line(item)?;
166            if line.as_ref().starts_with("#CXRLE") {
167                cxrle_data.replace(
168                    parse_cxrle(line.as_ref())
169                        .ok_or_else(|| Error::InvalidCxrleLine(line.as_ref().to_string()))?,
170                );
171            } else if line.as_ref().starts_with("x ") || line.as_ref().starts_with("x=") {
172                header_data.replace(
173                    parse_header(line.as_ref())
174                        .ok_or_else(|| Error::InvalidHeaderLine(line.as_ref().to_string()))?,
175                );
176            } else if !line.as_ref().starts_with('#') {
177                current_line = Some(I::bytes(line));
178                break;
179            }
180        }
181        if let Some(CxrleData { pos: Some(pos), .. }) = cxrle_data {
182            position = pos;
183            x_start = pos.0;
184        }
185        Ok(Self {
186            cxrle_data,
187            header_data,
188            lines,
189            current_line,
190            position,
191            x_start,
192            run_count: 0,
193            alive_count: 0,
194            state: 1,
195            state_prefix: None,
196            #[cfg(feature = "unknown")]
197            unknown: false,
198        })
199    }
200
201    /// Data from the `#CXRLE` line.
202    pub const fn cxrle_data(&self) -> Option<&CxrleData> {
203        self.cxrle_data.as_ref()
204    }
205
206    /// Data from the header line.
207    pub const fn header_data(&self) -> Option<&HeaderData> {
208        self.header_data.as_ref()
209    }
210
211    /// Allow unknown cells.
212    ///
213    /// In this variant of RLE format, there is another symbol, `?`,
214    /// which represents unknown cells. Now unknown cells are the background.
215    /// Dead cells at the end of each line must not be omitted.
216    /// The iterator will also explicitly output the dead cells.
217    #[cfg(feature = "unknown")]
218    #[cfg_attr(docs_rs, doc(cfg(feature = "unknown")))]
219    pub fn with_unknown(mut self) -> Self {
220        self.unknown = true;
221        self
222    }
223}
224
225impl<I, L> Rle<I>
226where
227    I: Input<Lines = L>,
228    L: Input,
229{
230    /// Parse the remaining unparsed lines as a new RLE.
231    pub fn remains(self) -> Result<Rle<L>, Error> {
232        Rle::new(self.lines)
233    }
234
235    /// Try to parse the remaining unparsed lines as a new RLE.
236    ///
237    /// Returns `Ok(None)` if the remaining lines is empty or only
238    /// contains header lines and comments.
239    pub fn try_remains(self) -> Result<Option<Rle<L>>, Error> {
240        let rle = Rle::new(self.lines)?;
241        Ok(if rle.current_line.is_some() {
242            Some(rle)
243        } else {
244            None
245        })
246    }
247}
248
249impl<R: Read> Rle<BufReader<R>> {
250    /// Creates a new parser instance from something that implements [`Read`] trait,
251    /// 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 Rle<I>
258where
259    I::Lines: Clone,
260    I::Bytes: Clone,
261{
262    fn clone(&self) -> Self {
263        Self {
264            cxrle_data: self.cxrle_data.clone(),
265            header_data: self.header_data.clone(),
266            lines: self.lines.clone(),
267            current_line: self.current_line.clone(),
268            position: self.position,
269            x_start: self.x_start,
270            run_count: self.run_count,
271            alive_count: self.alive_count,
272            state: self.state,
273            state_prefix: self.state_prefix,
274            #[cfg(feature = "unknown")]
275            unknown: self.unknown,
276        }
277    }
278}
279
280/// An iterator over living cells in an RLE file.
281impl<I: Input> Iterator for Rle<I> {
282    type Item = Result<CellData, Error>;
283
284    fn next(&mut self) -> Option<Self::Item> {
285        if self.alive_count > 0 {
286            self.alive_count -= 1;
287            let cell = CellData {
288                position: self.position,
289                state: self.state,
290            };
291            self.position.0 += 1;
292            return Some(Ok(cell));
293        }
294        loop {
295            if let Some(c) = self.current_line.as_mut().and_then(Iterator::next) {
296                if c.is_ascii_digit() {
297                    self.run_count = 10 * self.run_count + (c - b'0') as i64
298                } else if !c.is_ascii_whitespace() {
299                    if self.run_count == 0 {
300                        self.run_count = 1;
301                    }
302                    if self.state_prefix.is_some() && !(b'A'..=b'X').contains(&c) {
303                        let mut state_string = char::from(self.state_prefix.unwrap()).to_string();
304                        state_string.push(char::from(c));
305                        return Some(Err(Error::InvalidState(state_string)));
306                    }
307                    match c {
308                        #[cfg(feature = "unknown")]
309                        b'?' if self.unknown => {
310                            self.position.0 += self.run_count;
311                            self.run_count = 0;
312                        }
313                        #[cfg(feature = "unknown")]
314                        b'b' | b'.' | b'o' | b'A'..=b'X' if self.unknown => {
315                            match c {
316                                b'b' | b'.' => self.state = 0,
317                                b'o' => self.state = 1,
318                                _ => {
319                                    self.state =
320                                        24 * (self.state_prefix.take().unwrap_or(b'o') - b'o');
321                                    self.state += c + 1 - b'A';
322                                }
323                            }
324                            self.alive_count = self.run_count - 1;
325                            self.run_count = 0;
326                            let cell = CellData {
327                                position: self.position,
328                                state: self.state,
329                            };
330                            self.position.0 += 1;
331                            return Some(Ok(cell));
332                        }
333                        b'b' | b'.' => {
334                            self.position.0 += self.run_count;
335                            self.run_count = 0;
336                        }
337                        b'o' | b'A'..=b'X' => {
338                            if c == b'o' {
339                                self.state = 1;
340                            } else {
341                                self.state = 24 * (self.state_prefix.take().unwrap_or(b'o') - b'o');
342                                self.state += c + 1 - b'A';
343                            }
344                            self.alive_count = self.run_count - 1;
345                            self.run_count = 0;
346                            let cell = CellData {
347                                position: self.position,
348                                state: self.state,
349                            };
350                            self.position.0 += 1;
351                            return Some(Ok(cell));
352                        }
353                        b'p'..=b'y' => {
354                            self.state_prefix = Some(c);
355                        }
356                        b'$' => {
357                            self.position.0 = self.x_start;
358                            self.position.1 += self.run_count;
359                            self.run_count = 0;
360                        }
361                        b'!' => {
362                            self.current_line = None;
363                            return None;
364                        }
365                        _ => return Some(Err(Error::InvalidState(char::from(c).to_string()))),
366                    }
367                }
368            } else if let Some(item) = self.lines.next() {
369                match I::line(item) {
370                    Ok(line) => {
371                        if line.as_ref().starts_with('#')
372                            | line.as_ref().starts_with("x ")
373                            | line.as_ref().starts_with("x=")
374                        {
375                            continue;
376                        } else {
377                            self.current_line = Some(I::bytes(line));
378                        }
379                    }
380                    Err(e) => {
381                        return Some(Err(Error::IoError(e)));
382                    }
383                }
384            } else {
385                return None;
386            }
387        }
388    }
389}
390
391#[cfg(test)]
392mod tests {
393    use super::*;
394
395    #[test]
396    fn rle_parse_cxrle() {
397        assert_eq!(
398            parse_cxrle("#CXRLE"),
399            Some(CxrleData {
400                pos: None,
401                gen: None
402            })
403        );
404        assert_eq!(
405            parse_cxrle("#CXRLE Pos=0,-1377 Gen=3480106827776"),
406            Some(CxrleData {
407                pos: Some((0, -1377)),
408                gen: Some(3480106827776)
409            })
410        );
411        assert_eq!(
412            parse_cxrle("#CXRLE Gen = 3480106827776 Pos = 0, -1377"),
413            Some(CxrleData {
414                pos: Some((0, -1377)),
415                gen: Some(3480106827776)
416            })
417        );
418        assert_eq!(
419            parse_cxrle("#CXRLE211Pos=0,-9dcdcs2,[a ccGen=348sss1068cscPos= -333,-1a6"),
420            Some(CxrleData {
421                pos: Some((-333, -1)),
422                gen: Some(348)
423            })
424        );
425    }
426
427    #[test]
428    fn rle_parse_header() {
429        assert_eq!(parse_header("xxx"), None);
430        assert_eq!(
431            parse_header("x = 3, y = 3, rule = B3/S23"),
432            Some(HeaderData {
433                x: 3,
434                y: 3,
435                rule: Some(String::from("B3/S23"))
436            })
437        );
438        assert_eq!(
439            parse_header("x = 3, y = 3"),
440            Some(HeaderData {
441                x: 3,
442                y: 3,
443                rule: None
444            })
445        );
446        assert_eq!(parse_header("x = 3, y = -3"), None);
447        assert_eq!(
448            parse_header("x = 3, y = 3, rule = Conway's Game of Life  "),
449            Some(HeaderData {
450                x: 3,
451                y: 3,
452                rule: Some(String::from("Conway's Game of Life"))
453            })
454        );
455    }
456
457    #[test]
458    fn rle_glider() -> Result<(), Error> {
459        const GLIDER: &str = r"#N Glider
460#O Richard K. Guy
461#C The smallest, most common, and first discovered spaceship. Diagonal, has period 4 and speed c/4.
462#C www.conwaylife.com/wiki/index.php?title=Glider
463x = 3, y = 3, rule = B3/S23
464bob$2bo$3o!";
465
466        let glider = Rle::new(GLIDER)?;
467
468        let _ = glider.clone();
469
470        assert_eq!(glider.cxrle_data, None);
471        assert_eq!(
472            glider.header_data,
473            Some(HeaderData {
474                x: 3,
475                y: 3,
476                rule: Some(String::from("B3/S23"))
477            })
478        );
479
480        let cells = glider
481            .map(|res| res.map(|c| c.position))
482            .collect::<Result<Vec<_>, _>>()?;
483        assert_eq!(cells, vec![(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)]);
484        Ok(())
485    }
486
487    #[test]
488    fn rle_glider_cxrle() -> Result<(), Error> {
489        const GLIDER: &str = r"#CXRLE Pos=-1,-1
490x = 3, y = 3, rule = B3/S23
491bo$2bo$3o!";
492
493        let glider = Rle::new(GLIDER)?;
494
495        assert_eq!(
496            glider.cxrle_data,
497            Some(CxrleData {
498                pos: Some((-1, -1)),
499                gen: None
500            })
501        );
502        assert_eq!(
503            glider.header_data,
504            Some(HeaderData {
505                x: 3,
506                y: 3,
507                rule: Some(String::from("B3/S23"))
508            })
509        );
510
511        let cells = glider
512            .map(|res| res.map(|c| c.position))
513            .collect::<Result<Vec<_>, _>>()?;
514        assert_eq!(cells, vec![(0, -1), (1, 0), (-1, 1), (0, 1), (1, 1)]);
515        Ok(())
516    }
517
518    #[test]
519    fn rle_generations() -> Result<(), Error> {
520        const OSCILLATOR: &str = r"x = 3, y = 3, rule = 3457/357/5
5213A$B2A$.CD!";
522
523        let oscillator = Rle::new(OSCILLATOR)?;
524
525        assert_eq!(oscillator.cxrle_data, None);
526        assert_eq!(
527            oscillator.header_data,
528            Some(HeaderData {
529                x: 3,
530                y: 3,
531                rule: Some(String::from("3457/357/5"))
532            })
533        );
534
535        let cells = oscillator.collect::<Result<Vec<_>, _>>()?;
536        assert_eq!(
537            cells,
538            vec![
539                CellData {
540                    position: (0, 0),
541                    state: 1,
542                },
543                CellData {
544                    position: (1, 0),
545                    state: 1,
546                },
547                CellData {
548                    position: (2, 0),
549                    state: 1,
550                },
551                CellData {
552                    position: (0, 1),
553                    state: 2,
554                },
555                CellData {
556                    position: (1, 1),
557                    state: 1,
558                },
559                CellData {
560                    position: (2, 1),
561                    state: 1,
562                },
563                CellData {
564                    position: (1, 2),
565                    state: 3,
566                },
567                CellData {
568                    position: (2, 2),
569                    state: 4,
570                },
571            ]
572        );
573        Ok(())
574    }
575
576    #[test]
577    fn rle_generations_256() -> Result<(), Error> {
578        const OSCILLATOR: &str = r"x = 3, y = 3, rule = 23/3/256
579.AwH$vIxNrQ$2pU!";
580
581        let oscillator = Rle::new(OSCILLATOR)?;
582
583        assert_eq!(oscillator.cxrle_data, None);
584        assert_eq!(
585            oscillator.header_data,
586            Some(HeaderData {
587                x: 3,
588                y: 3,
589                rule: Some(String::from("23/3/256"))
590            })
591        );
592
593        let cells = oscillator.collect::<Result<Vec<_>, _>>()?;
594        assert_eq!(
595            cells,
596            vec![
597                CellData {
598                    position: (1, 0),
599                    state: 1,
600                },
601                CellData {
602                    position: (2, 0),
603                    state: 200,
604                },
605                CellData {
606                    position: (0, 1),
607                    state: 177,
608                },
609                CellData {
610                    position: (1, 1),
611                    state: 230,
612                },
613                CellData {
614                    position: (2, 1),
615                    state: 89,
616                },
617                CellData {
618                    position: (0, 2),
619                    state: 45,
620                },
621                CellData {
622                    position: (1, 2),
623                    state: 45,
624                },
625            ]
626        );
627        Ok(())
628    }
629
630    #[test]
631    fn rle_two_rles() -> Result<(), Error> {
632        const GLIDER: &str = r"#N Glider
633#O Richard K. Guy
634#C The smallest, most common, and first discovered spaceship. Diagonal, has period 4 and speed c/4.
635#C www.conwaylife.com/wiki/index.php?title=Glider
636x = 3, y = 3, rule = B3/S23
637bob$2bo$3o!
638#N Glider
639#O Richard K. Guy
640#C The smallest, most common, and first discovered spaceship. Diagonal, has period 4 and speed c/4.
641#C www.conwaylife.com/wiki/index.php?title=Glider
642x = 3, y = 3, rule = B3/S23
643bob$2bo$3o!";
644
645        let mut first_rle = Rle::new(GLIDER)?;
646
647        assert_eq!(first_rle.cxrle_data, None);
648        assert_eq!(
649            first_rle.header_data,
650            Some(HeaderData {
651                x: 3,
652                y: 3,
653                rule: Some(String::from("B3/S23"))
654            })
655        );
656
657        let mut cells = Vec::new();
658        for c in &mut first_rle {
659            cells.push(c?.position);
660        }
661        assert_eq!(cells, vec![(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)]);
662
663        let mut second_rle = first_rle.remains()?;
664        cells.clear();
665
666        for c in &mut second_rle {
667            cells.push(c?.position);
668        }
669
670        let third_rle = second_rle.try_remains()?;
671        assert!(third_rle.is_none());
672        Ok(())
673    }
674
675    #[test]
676    #[cfg(feature = "unknown")]
677    fn rle_glider_with_unknown() -> Result<(), Error> {
678        const GLIDER: &str = r"#CXRLE Pos=-1,-1
679x = 3, y = 3, rule = B3/S23
6805?$?bob?$?2bo?$?3o?$5?!";
681
682        let glider = Rle::new(GLIDER)?.with_unknown();
683
684        assert_eq!(
685            glider.cxrle_data(),
686            Some(&CxrleData {
687                pos: Some((-1, -1)),
688                gen: None
689            })
690        );
691        assert_eq!(
692            glider.header_data(),
693            Some(&HeaderData {
694                x: 3,
695                y: 3,
696                rule: Some(String::from("B3/S23"))
697            })
698        );
699
700        let cells = glider.collect::<Result<Vec<_>, _>>()?;
701        assert_eq!(
702            cells,
703            vec![
704                CellData {
705                    position: (0, 0),
706                    state: 0,
707                },
708                CellData {
709                    position: (1, 0),
710                    state: 1,
711                },
712                CellData {
713                    position: (2, 0),
714                    state: 0,
715                },
716                CellData {
717                    position: (0, 1),
718                    state: 0,
719                },
720                CellData {
721                    position: (1, 1),
722                    state: 0,
723                },
724                CellData {
725                    position: (2, 1),
726                    state: 1,
727                },
728                CellData {
729                    position: (0, 2),
730                    state: 1,
731                },
732                CellData {
733                    position: (1, 2),
734                    state: 1,
735                },
736                CellData {
737                    position: (2, 2),
738                    state: 1,
739                },
740            ]
741        );
742        Ok(())
743    }
744}
ca_formats/rle.rs

ca_formats/
rle.rs
