sgf_parse/
parser.rs

1use std::ptr::NonNull;
2
3use crate::go;
4use crate::lexer::{tokenize, LexerError, Token};
5use crate::unknown_game;
6use crate::{GameTree, GameType, SgfNode, SgfProp};
7
8/// Returns the [`GameTree`] values parsed from the provided text using default parsing options.
9///
10/// This function will attempt to convert non-FF\[4\] files to FF\[4\] if possible. Check out
11/// [`parse_with_options`] if you want to change the default behavior.
12///
13/// # Errors
14/// If the text can't be parsed as an SGF FF\[4\] collection, then an error is returned.
15///
16/// # Examples
17/// ```
18/// use sgf_parse::{parse, GameType};
19///
20/// let sgf = "(;SZ[9]C[Some comment];B[de];W[fe])(;B[de];W[ff])";
21/// let gametrees = parse(sgf).unwrap();
22/// assert!(gametrees.len() == 2);
23/// assert!(gametrees.iter().all(|gametree| gametree.gametype() == GameType::Go));
24/// ```
25pub fn parse(text: &str) -> Result<Vec<GameTree>, SgfParseError> {
26    parse_with_options(text, &ParseOptions::default())
27}
28
29/// Returns the [`GameTree`] values parsed from the provided text.
30///
31/// # Errors
32/// If the text can't be parsed as an SGF FF\[4\] collection, then an error is returned.
33///
34/// # Examples
35/// ```
36/// use sgf_parse::{parse_with_options, ParseOptions, GameType};
37///
38/// let sgf = "(;SZ[9]C[Some comment];B[de];W[fe])(;B[de];W[ff])";
39/// let gametrees = parse_with_options(sgf, &ParseOptions::default()).unwrap();
40/// assert!(gametrees.len() == 2);
41/// assert!(gametrees.iter().all(|gametree| gametree.gametype() == GameType::Go));
42/// ```
43pub fn parse_with_options(
44    text: &str,
45    options: &ParseOptions,
46) -> Result<Vec<GameTree>, SgfParseError> {
47    let tokens = tokenize(text)
48        .map(|result| match result {
49            Err(e) => Err(SgfParseError::LexerError(e)),
50            Ok((token, _span)) => Ok(token),
51        })
52        .collect::<Result<Vec<_>, _>>()?;
53    split_by_gametree(&tokens)?
54        .into_iter()
55        .map(|tokens| match find_gametype(tokens)? {
56            GameType::Go => parse_gametree::<go::Prop>(tokens, options),
57            GameType::Unknown => parse_gametree::<unknown_game::Prop>(tokens, options),
58        })
59        .collect::<Result<_, _>>()
60}
61
62/// Options for parsing SGF files.
63pub struct ParseOptions {
64    /// Whether to allow conversion of FF\[3\] mixed case identifiers to FF\[4\].
65    ///
66    /// All lower case letters are dropped.
67    /// This should allow parsing any older files which are valid, but not valid FF\[4\].
68    pub convert_mixed_case_identifiers: bool,
69}
70
71impl Default for ParseOptions {
72    fn default() -> Self {
73        ParseOptions {
74            convert_mixed_case_identifiers: true,
75        }
76    }
77}
78
79/// Error type for failures parsing sgf from text.
80#[derive(Debug, Clone, Copy, PartialEq, Eq)]
81pub enum SgfParseError {
82    LexerError(LexerError),
83    UnexpectedGameTreeStart,
84    UnexpectedGameTreeEnd,
85    UnexpectedProperty,
86    UnexpectedEndOfData,
87    UnexpectedGameType,
88    InvalidFF4Property,
89}
90
91impl From<LexerError> for SgfParseError {
92    fn from(error: LexerError) -> Self {
93        Self::LexerError(error)
94    }
95}
96
97impl std::fmt::Display for SgfParseError {
98    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
99        match self {
100            SgfParseError::LexerError(e) => write!(f, "Error tokenizing: {}", e),
101            SgfParseError::UnexpectedGameTreeStart => write!(f, "Unexpected start of game tree"),
102            SgfParseError::UnexpectedGameTreeEnd => write!(f, "Unexpected end of game tree"),
103            SgfParseError::UnexpectedProperty => write!(f, "Unexpected property"),
104            SgfParseError::UnexpectedEndOfData => write!(f, "Unexpected end of data"),
105            SgfParseError::UnexpectedGameType => write!(f, "Unexpected game type"),
106            SgfParseError::InvalidFF4Property => {
107                write!(
108                    f,
109                    "Invalid FF[4] property without `convert_mixed_case_identifiers`"
110                )
111            }
112        }
113    }
114}
115
116impl std::error::Error for SgfParseError {}
117
118// Split the tokens up into individual gametrees.
119//
120// This will let us easily scan each gametree for GM properties.
121// Only considers StartGameTree/EndGameTree tokens.
122fn split_by_gametree(tokens: &[Token]) -> Result<Vec<&[Token]>, SgfParseError> {
123    let mut gametrees = vec![];
124    let mut gametree_depth: u64 = 0;
125    let mut slice_start = 0;
126    for (i, token) in tokens.iter().enumerate() {
127        match token {
128            Token::StartGameTree => gametree_depth += 1,
129            Token::EndGameTree => {
130                if gametree_depth == 0 {
131                    return Err(SgfParseError::UnexpectedGameTreeEnd);
132                }
133                gametree_depth -= 1;
134                if gametree_depth == 0 {
135                    gametrees.push(&tokens[slice_start..=i]);
136                    slice_start = i + 1;
137                }
138            }
139            _ => {}
140        }
141    }
142    if gametree_depth != 0 {
143        return Err(SgfParseError::UnexpectedEndOfData);
144    }
145
146    Ok(gametrees)
147}
148
149// Parse a single gametree of a known type.
150fn parse_gametree<Prop: SgfProp>(
151    tokens: &[Token],
152    options: &ParseOptions,
153) -> Result<GameTree, SgfParseError>
154where
155    SgfNode<Prop>: std::convert::Into<GameTree>,
156{
157    // TODO: Rewrite this without `unsafe`
158    let mut collection: Vec<SgfNode<Prop>> = vec![];
159    // //// Pointer to the `Vec` of children we're currently building.
160    let mut current_node_list_ptr = NonNull::new(&mut collection).unwrap();
161    // Stack of pointers to incomplete `Vec`s of children.
162    let mut incomplete_child_lists: Vec<NonNull<Vec<SgfNode<Prop>>>> = vec![];
163    //// Using pointers involves some unsafe calls, but should be ok here.
164    //// Since pointers are always initialized from real structs, and those structs
165    //// live for the whole function body, our only safety concern is dangling pointers.
166    ////
167    //// Since we build the tree traversing depth-first those structs shouldn't be
168    //// modified while the pointer is live. Heap-allocated contents of their
169    //// `children` may be modified, but that shouldn't change anything.
170
171    let mut tokens = tokens.iter().peekable();
172    while let Some(token) = tokens.next() {
173        match token {
174            Token::StartGameTree => {
175                // SGF game trees must have a root node.
176                if let Some(node_list_ptr) = incomplete_child_lists.last() {
177                    let node_list = unsafe { node_list_ptr.as_ref() };
178                    if node_list.is_empty() {
179                        return Err(SgfParseError::UnexpectedGameTreeStart);
180                    }
181                }
182                incomplete_child_lists.push(current_node_list_ptr);
183            }
184            Token::EndGameTree => match incomplete_child_lists.pop() {
185                Some(node_list) => current_node_list_ptr = node_list,
186                None => return Err(SgfParseError::UnexpectedGameTreeEnd),
187            },
188            Token::StartNode => {
189                let mut new_node = SgfNode::default();
190                let mut prop_tokens = vec![];
191                while let Some(Token::Property(_)) = tokens.peek() {
192                    prop_tokens.push(tokens.next().unwrap());
193                }
194                for token in prop_tokens {
195                    match token {
196                        // TODO: Consider refactoring to consume tokens and clone of values.
197                        Token::Property((identifier, values)) => {
198                            let identifier = {
199                                if identifier.chars().all(|c| c.is_ascii_uppercase()) {
200                                    identifier.clone()
201                                } else if options.convert_mixed_case_identifiers {
202                                    identifier
203                                        .chars()
204                                        .filter(|c| c.is_ascii_uppercase())
205                                        .collect()
206                                } else {
207                                    return Err(SgfParseError::InvalidFF4Property);
208                                }
209                            };
210                            new_node
211                                .properties
212                                .push(Prop::new(identifier, values.clone()))
213                        }
214                        _ => unreachable!(),
215                    }
216                }
217                let node_list = unsafe { current_node_list_ptr.as_mut() };
218                node_list.push(new_node);
219                current_node_list_ptr =
220                    NonNull::new(&mut node_list.last_mut().unwrap().children).unwrap();
221            }
222            Token::Property(_) => return Err(SgfParseError::UnexpectedProperty),
223        }
224    }
225
226    if !incomplete_child_lists.is_empty() || collection.len() != 1 {
227        return Err(SgfParseError::UnexpectedEndOfData);
228    }
229    let mut root_node = collection.into_iter().next().unwrap();
230    root_node.is_root = true;
231    Ok(root_node.into())
232}
233
234// Figure out which game to parse from a slice of tokens.
235//
236// This function is necessary because we need to know the game before we can do the parsing.
237fn find_gametype(tokens: &[Token]) -> Result<GameType, SgfParseError> {
238    match find_gametree_root_prop_values("GM", tokens)? {
239        None => Ok(GameType::Go),
240        Some(values) => {
241            if values.len() != 1 {
242                return Ok(GameType::Unknown);
243            }
244            match values[0].as_str() {
245                "1" => Ok(GameType::Go),
246                _ => Ok(GameType::Unknown),
247            }
248        }
249    }
250}
251
252// Find the property values for a given identifier in the root node from the gametree's tokens.
253//
254// We use this to determine key root properties (like GM and FF) before parsing.
255// Returns an error if there's more than one match.
256fn find_gametree_root_prop_values<'a>(
257    prop_ident: &'a str,
258    tokens: &'a [Token],
259) -> Result<Option<&'a Vec<String>>, SgfParseError> {
260    // Find the matching property values in the first node.
261    // Skip the initial StartGameTree, StartNode tokens; we'll handle any errors later.
262    let matching_tokens: Vec<&Vec<String>> = tokens
263        .iter()
264        .skip(2)
265        .take_while(|&token| matches!(token, Token::Property(_)))
266        .filter_map(move |token| match token {
267            Token::Property((ident, values)) if ident == prop_ident => Some(values),
268            _ => None,
269        })
270        .collect();
271
272    match matching_tokens.len() {
273        0 => Ok(None),
274        1 => Ok(Some(matching_tokens[0])),
275        _ => Err(SgfParseError::UnexpectedProperty),
276    }
277}
278
279#[cfg(test)]
280mod test {
281    use super::*;
282    use crate::{go, serialize};
283
284    fn load_test_sgf() -> Result<String, Box<dyn std::error::Error>> {
285        // See https://www.red-bean.com/sgf/examples/
286        let mut sgf_path = std::path::PathBuf::from(env!("CARGO_MANIFEST_DIR"));
287        sgf_path.push("resources/test/ff4_ex.sgf");
288        let data = std::fs::read_to_string(sgf_path)?;
289
290        Ok(data)
291    }
292
293    fn get_go_nodes() -> Result<Vec<SgfNode<go::Prop>>, Box<dyn std::error::Error>> {
294        let data = load_test_sgf()?;
295
296        Ok(go::parse(&data)?)
297    }
298
299    fn node_depth(mut sgf_node: &SgfNode<go::Prop>) -> u64 {
300        let mut depth = 1;
301        while sgf_node.children().count() > 0 {
302            depth += 1;
303            sgf_node = sgf_node.children().next().unwrap();
304        }
305        depth
306    }
307
308    #[test]
309    fn sgf_has_two_gametrees() {
310        let sgf_nodes = get_go_nodes().unwrap();
311        assert_eq!(sgf_nodes.len(), 2);
312    }
313
314    #[test]
315    fn gametree_one_has_five_variations() {
316        let sgf_nodes = get_go_nodes().unwrap();
317        let sgf_node = &sgf_nodes[0];
318        assert_eq!(sgf_node.children().count(), 5);
319    }
320
321    #[test]
322    fn gametree_one_has_size_19() {
323        let sgf_nodes = get_go_nodes().unwrap();
324        let sgf_node = &sgf_nodes[0];
325        match sgf_node.get_property("SZ") {
326            Some(go::Prop::SZ(size)) => assert_eq!(size, &(19, 19)),
327            _ => unreachable!("Expected size property"),
328        }
329    }
330
331    #[test]
332    fn gametree_variation_depths() {
333        let sgf_nodes = get_go_nodes().unwrap();
334        let sgf_node = &sgf_nodes[0];
335        let children: Vec<_> = sgf_node.children().collect();
336        assert_eq!(node_depth(children[0]), 13);
337        assert_eq!(node_depth(children[1]), 4);
338        assert_eq!(node_depth(children[2]), 4);
339    }
340
341    #[test]
342    fn gametree_two_has_one_variation() {
343        let sgf_nodes = get_go_nodes().unwrap();
344        let sgf_node = &sgf_nodes[1];
345        assert_eq!(sgf_node.children().count(), 1);
346    }
347
348    #[test]
349    fn serialize_then_parse() {
350        let data = load_test_sgf().unwrap();
351        let gametrees = parse(&data).unwrap();
352        let text = serialize(&gametrees);
353        assert_eq!(gametrees, parse(&text).unwrap());
354    }
355
356    #[test]
357    fn invalid_property() {
358        let input = "(;GM[1]W[rp.pmonpoqprpsornqmpm])";
359        let sgf_nodes = go::parse(input).unwrap();
360        let expected = vec![
361            go::Prop::GM(1),
362            go::Prop::Invalid("W".to_string(), vec!["rp.pmonpoqprpsornqmpm".to_string()]),
363        ];
364
365        assert_eq!(sgf_nodes.len(), 1);
366        let sgf_node = &sgf_nodes[0];
367        assert_eq!(sgf_node.properties().cloned().collect::<Vec<_>>(), expected);
368    }
369
370    #[test]
371    fn unknown_game() {
372        let input = "(;GM[37]W[rp.pmonpoqprpsornqmpm])";
373        let gametrees = parse(input).unwrap();
374        assert_eq!(gametrees.len(), 1);
375        assert_eq!(gametrees[0].gametype(), GameType::Unknown);
376        let sgf_node = match &gametrees[0] {
377            GameTree::Unknown(node) => node,
378            _ => panic!("Unexpected game type"),
379        };
380        let expected = vec![
381            unknown_game::Prop::GM(37),
382            unknown_game::Prop::W("rp.pmonpoqprpsornqmpm".into()),
383        ];
384
385        assert_eq!(sgf_node.properties().cloned().collect::<Vec<_>>(), expected);
386    }
387
388    #[test]
389    fn mixed_games() {
390        let input = "(;GM[1];W[dd])(;GM[37]W[rp.pmonpoqprpsornqmpm])";
391        let gametrees = parse(input).unwrap();
392        assert_eq!(gametrees.len(), 2);
393        assert_eq!(gametrees[0].gametype(), GameType::Go);
394        assert_eq!(gametrees[1].gametype(), GameType::Unknown);
395    }
396
397    #[test]
398    fn stack_overflow() {
399        // This input generated a stack overflow with the old code
400        let input = "(;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;)";
401        let result = parse(&input);
402        assert!(result.is_ok());
403    }
404
405    #[test]
406    fn converts_up_ff3_property() {
407        let input = "(;GM[1]FF[3]CoPyright[test])";
408        let expected = vec![
409            go::Prop::GM(1),
410            go::Prop::FF(3),
411            go::Prop::CP("test".into()),
412        ];
413
414        let sgf_nodes = go::parse(input).unwrap();
415
416        assert_eq!(sgf_nodes.len(), 1);
417        let properties = sgf_nodes[0].properties().cloned().collect::<Vec<_>>();
418        assert_eq!(properties, expected);
419    }
420
421    #[test]
422    fn doesnt_convert_if_not_allowed() {
423        let input = "(;GM[1]FF[3]CoPyright[test])";
424        let parse_options = ParseOptions {
425            convert_mixed_case_identifiers: false,
426            ..ParseOptions::default()
427        };
428        let result = parse_with_options(input, &parse_options);
429        assert_eq!(result, Err(SgfParseError::InvalidFF4Property));
430    }
431
432    #[test]
433    fn compressed_list_for_unknown_game() {
434        let input = "(;GM[]MA[a:b])";
435        let gametree = parse(&input).unwrap().pop().unwrap();
436        let node = match gametree {
437            GameTree::Unknown(node) => node,
438            _ => panic!("Expected Unknown Game type"),
439        };
440        match node.get_property("MA") {
441            Some(unknown_game::Prop::MA(values)) => {
442                assert_eq!(values.len(), 1);
443                assert!(values.contains("a:b"));
444            }
445            _ => panic!("MA prop not found"),
446        }
447    }
448}
sgf_parse/parser.rs

sgf_parse/
parser.rs
