libdot_parse/
lib.rs

1extern crate dot;
2
3use std::collections::HashMap;
4use std::fmt;
5
6macro_rules! matches(
7    ($e:expr, $p:pat) => (
8        match $e {
9            $p => true,
10            _ => false
11        }
12    )
13);
14
15fn unwrap_to_printable<'a>(id: &'a Option<dot::Id<'_>>) -> Option<&'a str> {
16    match &id {
17        None => None,
18        Some(a) => Some(a.as_slice()),
19    }
20}
21
22trait Parsable<'t> {
23    type Output;
24    fn parse_from(edgeop: &'t str, tokens: &[&'t str]) -> Result<Self::Output, (usize, &'t str)>;
25}
26
27#[derive(Copy, Clone)]
28enum CompassPt {
29    N,
30    NE,
31    E,
32    SE,
33    S,
34    SW,
35    W,
36    NW,
37    C,
38    UND,
39}
40
41impl fmt::Debug for CompassPt {
42    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
43        let comp_str = match self {
44            CompassPt::N => "N",
45            CompassPt::NE => "NE",
46            CompassPt::E => "E",
47            CompassPt::SE => "SE",
48            CompassPt::S => "S",
49            CompassPt::SW => "SW",
50            CompassPt::W => "W",
51            CompassPt::NW => "NW",
52            CompassPt::C => "C",
53            CompassPt::UND => "UND",
54        };
55        write!(f, "{:?}", comp_str)
56    }
57}
58
59// This is to help parse: ID '=' ID.
60struct AssignmentStmt<'a> {
61    lhs: IdWrapper<'a>,
62    rhs: IdWrapper<'a>,
63}
64
65impl<'a> Parsable<'a> for AssignmentStmt<'a> {
66    type Output = AssignmentStmt<'a>;
67    // |edgeop| is ignored.
68    fn parse_from(_edgeop: &'a str, tokens: &[&'a str]) -> Result<Self::Output, (usize, &'a str)> {
69        match &tokens[..] {
70            [lhs_str, "=", rhs_str] => match (IdWrapper::new(lhs_str), IdWrapper::new(rhs_str)) {
71                (Ok(lhs), Ok(rhs)) => Ok(AssignmentStmt { lhs: lhs, rhs: rhs }),
72                (Err(_), _) => Err((0, "Invalid ID")),
73                (_, Err(_)) => Err((2, "Invalid ID")),
74            },
75            _ => Err((1, "Expect '='")),
76        }
77    }
78}
79
80#[derive(Default)]
81pub struct Stmt<'a> {
82    node_stmt: Option<NodeStmt<'a>>,
83    edge_stmt: Option<EdgeStmt<'a>>,
84    attr_stmt: Option<AttrStmt<'a>>,
85    assign_stmt: Option<AssignmentStmt<'a>>,
86    subgraph: Option<SubGraph<'a>>,
87}
88
89impl fmt::Debug for Stmt<'_> {
90    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
91        if self.node_stmt.is_some() {
92            return write!(f, "NodeStmt{{..}}")
93        }
94        if self.edge_stmt.is_some() {
95            return write!(f, "EdgeStmt{{..}}")
96        }
97        if self.attr_stmt.is_some() {
98            return write!(f, "AttrStmt{{..}}")
99        }
100        if self.assign_stmt.is_some() {
101            return write!(f, "AssignStmt{{..}}")
102        }
103        if self.subgraph.is_some() {
104            return write!(f, "SubGraph{{..}}")
105        }
106        return Err(fmt::Error);
107    }
108}
109
110impl<'a> Stmt<'a> {
111    fn parse_from(edgeop: &'a str, tokens: &[&'a str]) -> Result<Stmt<'a>, (usize, &'a str)> {
112        fn try_different_stmt<'b, T: Parsable<'b, Output = T>>(
113            tokens_internal: &[&'b str],
114            edgeop: &'b str,
115            idx_err: &mut usize,
116            err_msg: &mut String,
117        ) -> Option<T> {
118            match T::parse_from(&edgeop, &tokens_internal) {
119                Err((idx_err_edge, err_msg_edge)) => {
120                    if idx_err_edge < *idx_err {
121                        *idx_err = idx_err_edge;
122                        *err_msg = err_msg_edge.to_string();
123                    }
124                    None
125                }
126                Ok(stmt) => Some(stmt),
127            }
128        }
129
130        let mut result = Stmt {
131            ..Default::default()
132        };
133        let mut idx_err: usize = tokens.len();
134        let mut err_msg = String::new();
135
136        if let Some(node_stmt) =
137            try_different_stmt::<NodeStmt>(&tokens, &edgeop, &mut idx_err, &mut err_msg)
138        {
139            result.node_stmt = Some(node_stmt);
140            Ok(result)
141        } else if let Some(edge_stmt) =
142            try_different_stmt::<EdgeStmt>(&tokens, &edgeop, &mut idx_err, &mut err_msg)
143        {
144            result.edge_stmt = Some(edge_stmt);
145            Ok(result)
146        } else if let Some(attr_stmt) =
147            try_different_stmt::<AttrStmt>(&tokens, &edgeop, &mut idx_err, &mut err_msg)
148        {
149            result.attr_stmt = Some(attr_stmt);
150            Ok(result)
151        } else if let Some(assign_stmt) =
152            try_different_stmt::<AssignmentStmt>(&tokens, &edgeop, &mut idx_err, &mut err_msg)
153        {
154            result.assign_stmt = Some(assign_stmt);
155            Ok(result)
156        } else if let Some(sub_graph) =
157            try_different_stmt::<SubGraph>(&tokens, &edgeop, &mut idx_err, &mut err_msg)
158        {
159            result.subgraph = Some(sub_graph);
160            Ok(result)
161        } else {
162            Err((0, ""))
163        }
164    }
165}
166
167struct StmtList<'a>(Vec<Stmt<'a>>);
168
169impl fmt::Debug for StmtList<'_> {
170    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
171        write!(f, "{:?}", self.0)
172    }
173}
174
175impl StmtList<'_> {
176    fn parse_from<'a>(
177        edgeop: &'a str,
178        tokens: &[&'a str],
179    ) -> Result<StmtList<'a>, (usize, &'a str)> {
180        if tokens.len() == 0 {
181            return Ok(StmtList(vec![]));
182        }
183        if let Ok(stmt) = Stmt::parse_from(edgeop, tokens) {
184            return Ok(StmtList(vec![stmt]));
185        }
186        for (token_idx, token) in tokens.iter().enumerate() {
187            // TODO: per standard, ';' is optional.
188            if token == &";" {
189                match (
190                    Stmt::parse_from(edgeop, &tokens[0..token_idx]),
191                    StmtList::parse_from(edgeop, &tokens[token_idx + 1..]),
192                ) {
193                    (Ok(stmt), Ok(mut stmt_list)) => {
194                        stmt_list.0.insert(0, stmt);
195                        return Ok(stmt_list);
196                    }
197                    _ => {}
198                }
199            }
200        }
201        // TODO: give reasonable err position.
202        Err((0, "failed parsing statement list."))
203    }
204}
205
206#[derive(Default)]
207pub struct Port<'a> {
208    id: Option<dot::Id<'a>>,
209    compass_pt: Option<CompassPt>,
210}
211
212impl fmt::Debug for Port<'_> {
213    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
214        write!(
215            f,
216            "Port{{id={:?}, compass={:?}}}",
217            unwrap_to_printable(&self.id),
218            self.compass_pt
219        )
220    }
221}
222
223impl PartialEq for Port<'_> {
224    fn eq(&self, other: &Self) -> bool {
225        fn id_match(lhs: &Port, rhs: &Port) -> bool {
226            match ((*lhs).id.as_ref(), (*rhs).id.as_ref()) {
227                (None, None) => true,
228                (Some(a), Some(b)) => a.as_slice() == b.as_slice(),
229                _ => false,
230            }
231        }
232
233        match (self.compass_pt, other.compass_pt) {
234            (None, None) => id_match(self, other),
235            (Some(a), Some(_b)) => matches!(a, _b) && id_match(self, other),
236            _ => false,
237        }
238    }
239}
240
241impl<'a> Port<'a> {
242    fn parse_from(tokens: &[&'a str]) -> Result<Port<'a>, ()> {
243        fn parse_compass_pt_from(token: &str) -> Result<CompassPt, ()> {
244            match token {
245                "n" => Ok(CompassPt::N),
246                "ne" => Ok(CompassPt::NE),
247                "e" => Ok(CompassPt::E),
248                "se" => Ok(CompassPt::SE),
249                "s" => Ok(CompassPt::S),
250                "sw" => Ok(CompassPt::SW),
251                "w" => Ok(CompassPt::W),
252                "nw" => Ok(CompassPt::NW),
253                "c" => Ok(CompassPt::C),
254                "_" => Ok(CompassPt::UND),
255                _ => Err(()),
256            }
257        };
258
259        if tokens.len() == 2 {
260            if tokens[0] != ":" {
261                return Err(());
262            } else {
263                match parse_compass_pt_from(tokens[1]) {
264                    Ok(comp) => Ok(Port {
265                        compass_pt: Some(comp),
266                        ..Default::default()
267                    }),
268                    Err(_) => match dot::Id::new(tokens[1]) {
269                        Ok(id) => Ok(Port {
270                            id: Some(id),
271                            ..Default::default()
272                        }),
273                        Err(_) => Err(()),
274                    },
275                }
276            }
277        } else if tokens.len() == 4 {
278            if tokens[0] != ":" || tokens[2] != ":" {
279                return Err(());
280            } else {
281                match parse_compass_pt_from(tokens[3]) {
282                    Err(_) => Err(()),
283                    Ok(comp) => match dot::Id::new(tokens[1]) {
284                        Ok(id) => Ok(Port {
285                            id: Some(id),
286                            compass_pt: Some(comp),
287                        }),
288                        Err(_) => Err(()),
289                    },
290                }
291            }
292        } else {
293            Err(())
294        }
295    }
296}
297
298struct IdWrapper<'a>(dot::Id<'a>);
299
300impl<'a> fmt::Debug for IdWrapper<'a> {
301    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
302        write!(f, "{:?}", self.0.as_slice())
303    }
304}
305
306impl<'a> PartialEq for IdWrapper<'a> {
307    fn eq(&self, other: &Self) -> bool {
308        self.0.as_slice() == other.0.as_slice()
309    }
310}
311
312impl<'a> PartialEq<&str> for IdWrapper<'a> {
313    fn eq(&self, other: &&str) -> bool {
314        self.0.as_slice() == *other
315    }
316}
317
318impl<'a> IdWrapper<'a> {
319    fn new(name: &'a str) -> Result<IdWrapper<'a>, ()> {
320        match (name, dot::Id::new(name)) {
321            ("graph", _) => Err(()),
322            ("node", _) => Err(()),
323            ("edge", _) => Err(()),
324            ("digraph", _) => Err(()),
325            ("strict", _) => Err(()),
326            (_, Err(_)) => Err(()),
327            (_, Ok(id)) => Ok(IdWrapper(id)),
328        }
329    }
330}
331
332pub struct NodeId<'a> {
333    id: IdWrapper<'a>,
334    port: Option<Port<'a>>,
335}
336
337impl fmt::Debug for NodeId<'_> {
338    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
339        write!(f, "NodeId{{id={:?}, port={:?}}}", self.id, self.port)
340    }
341}
342
343impl PartialEq for NodeId<'_> {
344    fn eq(&self, other: &Self) -> bool {
345        self.id == other.id && self.port == other.port
346    }
347}
348
349impl<'a> NodeId<'a> {
350    fn parse_from(tokens: &[&'a str]) -> Result<NodeId<'a>, ((usize, &'a str))> {
351        fn parse_option_port_from<'b>(
352            tokens: &[&'b str],
353        ) -> Result<Option<Port<'b>>, (usize, &'b str)> {
354            if tokens.len() == 0 {
355                return Ok(None);
356            }
357            match Port::parse_from(tokens) {
358                Ok(port) => Ok(Some(port)),
359                Err(_) => Err((0, "error parsing port")),
360            }
361        };
362
363        if tokens.len() == 0 {
364            return Err((0, "expecting node id"));
365        }
366        match IdWrapper::new(tokens[0]) {
367            Err(_) => Err((0, "cannot be used as id")),
368            Ok(id) => match parse_option_port_from(&tokens[1..]) {
369                Err((idx_err, err_msg)) => Err((idx_err + 1, err_msg)),
370                Ok(port) => Ok(NodeId { id: id, port: port }),
371            },
372        }
373    }
374}
375
376struct AList<'a>(HashMap<std::borrow::Cow<'a, str>, IdWrapper<'a>>);
377
378impl<'a> fmt::Debug for AList<'a> {
379    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
380        write!(f, "{:?}", self.0)
381    }
382}
383
384impl<'a> AList<'a> {
385    fn parse_from(tokens: &[&'a str]) -> Result<AList<'a>, (usize, &'a str)> {
386        fn parse_helper<'b>(
387            tokens: &[&'b str],
388            slice_idx: usize,
389        ) -> Result<AList<'b>, (usize, &'b str)> {
390            match (
391                AssignmentStmt::parse_from("", &tokens[0..3]),
392                AList::parse_from(&tokens[slice_idx..]),
393            ) {
394                (Ok(assignment), Ok(mut sub_list)) => {
395                    sub_list.0.insert(assignment.lhs.0.name(), assignment.rhs);
396                    Ok(sub_list)
397                }
398                (Err(err_info), _) => Err(err_info),
399                (_, Err((idx_err, err_msg))) => Err((idx_err + 3, err_msg)),
400            }
401        };
402
403        match tokens.len() {
404            0 => Ok(AList::new()),
405            // exclusive range is experimental
406            1 => Err((0, "Expecting assignment statement")),
407            2 => Err((0, "Expecting assignment statement")),
408            3 => parse_helper(tokens, 3),
409            _ => match tokens[3] {
410                ";" => parse_helper(tokens, 4),
411                "," => parse_helper(tokens, 4),
412                _ => parse_helper(tokens, 3),
413            },
414        }
415    }
416
417    fn new() -> AList<'a> {
418        AList(HashMap::new())
419    }
420
421    fn get(&self, key: &str) -> Option<&IdWrapper<'a>> {
422        self.0.get(std::borrow::Borrow::borrow(key))
423    }
424
425    fn len(&self) -> usize {
426        self.0.len()
427    }
428}
429
430struct AttrList<'a>(Vec<AList<'a>>);
431
432impl<'a> fmt::Debug for AttrList<'a> {
433    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
434        write!(f, "{:?}", self.0)
435    }
436}
437
438impl AttrList<'_> {
439    fn parse_from<'a>(tokens: &[&'a str]) -> Result<AttrList<'a>, (usize, &'a str)> {
440        // Recursive closure not allowed.
441        struct Internal {}
442        impl Internal {
443            fn parse_helper<'b>(tokens: &[&'b str]) -> Result<AttrList<'b>, (usize, &'b str)> {
444                match tokens.first() {
445                    None => Ok(AttrList(vec![])),
446                    Some(&"[") => match tokens.iter().position(|x| x == &"]") {
447                        None => Err((tokens.len(), &"expecting ']'")),
448                        Some(idx_right_bracket) => {
449                            match Self::parse_helper(&tokens[idx_right_bracket + 1..]) {
450                                Err((idx_err, err_msg)) => {
451                                    Err((idx_err + idx_right_bracket + 1, err_msg))
452                                }
453                                Ok(mut sub_attr_list) => {
454                                    match AList::parse_from(&tokens[1..idx_right_bracket]) {
455                                        Err(_) => Err((1, &"internal error")),
456                                        Ok(a_list) => {
457                                            sub_attr_list.0.push(a_list);
458                                            Ok(sub_attr_list)
459                                        }
460                                    }
461                                }
462                            }
463                        }
464                    },
465                    _ => Err((0, &"expecting '['")),
466                }
467            }
468        }
469
470        match Internal::parse_helper(tokens) {
471            Err(err_info) => Err(err_info),
472            Ok(result) => match result.0.len() {
473                0 => Err((0, &"expecting valid AttrList here")),
474                _ => Ok(result),
475            },
476        }
477    }
478}
479
480enum AttrStmtKey {
481    GRAPH,
482    NODE,
483    EDGE,
484}
485
486impl PartialEq for AttrStmtKey {
487    fn eq(&self, other: &Self) -> bool {
488        matches!(self, other)
489    }
490}
491
492impl fmt::Debug for AttrStmtKey {
493    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
494        let s = match self {
495            AttrStmtKey::GRAPH => "GRAPH",
496            AttrStmtKey::NODE => "NODE",
497            AttrStmtKey::EDGE => "EDGE",
498        };
499        write!(f, "{:?}", s)
500    }
501}
502
503pub struct AttrStmt<'a> {
504    key: AttrStmtKey,
505    attr_list: AttrList<'a>,
506}
507
508impl<'a> Parsable<'a> for AttrStmt<'a> {
509    type Output = AttrStmt<'a>;
510    // |edgeop| is ignored.
511    fn parse_from(_edgeop: &'a str, tokens: &[&'a str]) -> Result<Self::Output, (usize, &'a str)> {
512        let parse_helper =
513            |attr_key: AttrStmtKey, tokens: &[&'a str]| -> Result<AttrStmt<'a>, (usize, &'a str)> {
514                match AttrList::parse_from(&tokens[1..]) {
515                    Err((idx_err, err_msg)) => Err((idx_err + 1, err_msg)),
516                    Ok(attr_list) => Ok(AttrStmt {
517                        key: attr_key,
518                        attr_list: attr_list,
519                    }),
520                }
521            };
522
523        match tokens.first() {
524            Some(&"graph") => parse_helper(AttrStmtKey::GRAPH, &tokens),
525            Some(&"node") => parse_helper(AttrStmtKey::NODE, &tokens),
526            Some(&"edge") => parse_helper(AttrStmtKey::EDGE, &tokens),
527            _ => Err((0, &"AttrStmt must starts with graph|node|edge")),
528        }
529    }
530}
531
532pub struct NodeStmt<'a> {
533    id: NodeId<'a>,
534    attr_list: Option<AttrList<'a>>,
535}
536
537// impl<'a> fmt::Debug for NodeStmt<'a> {
538//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
539//         let s = match self.attr_list {
540//             None => format!("NodeStmt{{id={:?}}}", self.id),
541//             Some(attr_list) => format!("NodeStmt{{id={:?}, attr_list={:?}}}", self.id, attr_list),
542//         };
543//         write!(f, "{:?}", s)
544//     }
545// }
546
547impl<'a> Parsable<'a> for NodeStmt<'a> {
548    type Output = NodeStmt<'a>;
549    // |edgeop| is ignored.
550    fn parse_from(_edgeop: &'a str, tokens: &[&'a str]) -> Result<Self::Output, (usize, &'a str)> {
551        match tokens.iter().position(|x| x == &"[") {
552            None => match NodeId::parse_from(tokens) {
553                Err(err_info) => Err(err_info),
554                Ok(node_id) => Ok(NodeStmt {
555                    id: node_id,
556                    attr_list: None,
557                }),
558            },
559            Some(idx_left_bracket) => {
560                match (
561                    NodeId::parse_from(&tokens[..idx_left_bracket]),
562                    AttrList::parse_from(&tokens[idx_left_bracket..]),
563                ) {
564                    (Ok(node_id), Ok(attr_list)) => Ok(NodeStmt {
565                        id: node_id,
566                        attr_list: Some(attr_list),
567                    }),
568                    (Err(err_info), _) => Err(err_info),
569                    (Ok(_), Err((idx_err, err_msg))) => Err((idx_err + idx_left_bracket, err_msg)),
570                }
571            }
572        }
573    }
574}
575
576pub struct SubGraph<'a> {
577    id: Option<dot::Id<'a>>,
578    stmt_list: StmtList<'a>,
579}
580
581impl<'a> Parsable<'a> for SubGraph<'a> {
582    type Output = SubGraph<'a>;
583    // |edgeop| is ignored.
584    fn parse_from(edgeop: &'a str, tokens: &[&'a str]) -> Result<SubGraph<'a>, (usize, &'a str)> {
585        let parse_stmt_list_and_return = |id: Option<dot::Id<'a>>,
586                                          id_stmt_start: usize|
587         -> Result<SubGraph<'a>, (usize, &'a str)> {
588            match StmtList::parse_from(edgeop, &tokens[id_stmt_start..tokens.len() - 1]) {
589                Err((idx_err, err_msg)) => Err((idx_err + id_stmt_start, err_msg)),
590                Ok(stmt_list) => Ok(SubGraph {
591                    id: id,
592                    stmt_list: stmt_list,
593                }),
594            }
595        };
596
597        let key_subgraph: &str = "subgraph";
598        let right_brace: &str = "}";
599        match (tokens.iter().position(|x| x == &"{"), tokens.last()) {
600            (Some(idx_left_brace), Some(&right_brace)) => match idx_left_brace {
601                0 => parse_stmt_list_and_return(None, 1),
602                1 => match tokens[0] {
603                    key_subgraph => parse_stmt_list_and_return(None, 2),
604                    _ => Err((0, "expecting subgraph")),
605                },
606                2 => match (tokens[0], dot::Id::new(tokens[1])) {
607                    (_, Err(_)) => Err((1, "expecting valid id")),
608                    (key_subgraph, Ok(id)) => parse_stmt_list_and_return(Some(id), 3),
609                    (_, Ok(_)) => Err((0, "expecting subgraph")),
610                },
611                _ => Err((idx_left_brace, "wrong grammer")),
612            },
613            (None, _) => Err((0, "expecting '{'")),
614            (_, None) => Err((tokens.len(), "expecting '}'")),
615        }
616    }
617}
618
619type NodeOrSubgraph<'b> = (Option<NodeId<'b>>, Option<SubGraph<'b>>, (usize, &'b str));
620
621fn parse_node_or_subgraph<'a>(tokens_n_s: &[&'a str]) -> NodeOrSubgraph<'a> {
622    match (
623        NodeId::parse_from(tokens_n_s),
624        SubGraph::parse_from("", tokens_n_s),
625    ) {
626        (Ok(node_id), _) => (Some(node_id), None, (0, "")),
627        (_, Ok(subgraph)) => (None, Some(subgraph), (0, "")),
628        (Err((idx_err_node, err_msg_node)), Err((idx_err_subg, err_msg_subg))) => {
629            // If we move more forward when parsing node, guess it's a node.
630            if idx_err_node >= idx_err_subg {
631                (None, None, (idx_err_node, err_msg_node))
632            } else {
633                (None, None, (idx_err_subg, err_msg_subg))
634            }
635        }
636    }
637}
638
639#[derive(Default)]
640pub struct EdgeRhs<'a> {
641    // It stores a sequence of node_id or subgraph.
642    node_id_or_subgraph: Vec<(Option<NodeId<'a>>, Option<SubGraph<'a>>)>,
643}
644
645impl<'a> EdgeRhs<'a> {
646    fn parse_from(edgeop: &'a str, tokens: &[&'a str]) -> Result<EdgeRhs<'a>, (usize, &'a str)> {
647        // Helper function for recursive call.
648        fn parse_internal<'b>(
649            edgeop: &'b str,
650            tokens_internal: &[&'b str],
651        ) -> Result<EdgeRhs<'b>, (usize, &'b str)> {
652            let merge_and_return = |node_or_subgraph: NodeOrSubgraph<'b>,
653                                    idx_res_tokens_start: usize,
654                                    res_tokens: &[&'b str]|
655             -> Result<EdgeRhs<'b>, (usize, &'b str)> {
656                match node_or_subgraph {
657                    (None, None, (idx_err, err_msg)) => Err((idx_err, err_msg)),
658                    (Some(node_id), None, _) => match parse_internal(edgeop, res_tokens) {
659                        Err((idx_sub_err, sub_err_msg)) => {
660                            Err((idx_sub_err + idx_res_tokens_start, sub_err_msg))
661                        }
662                        Ok(mut sub_rhs) => {
663                            sub_rhs.node_id_or_subgraph.insert(0, (Some(node_id), None));
664                            Ok(sub_rhs)
665                        }
666                    },
667                    (None, Some(subgraph), _) => match parse_internal(edgeop, res_tokens) {
668                        Err((idx_sub_err, sub_err_msg)) => {
669                            Err((idx_sub_err + idx_res_tokens_start, sub_err_msg))
670                        }
671                        Ok(mut sub_rhs) => {
672                            sub_rhs
673                                .node_id_or_subgraph
674                                .insert(0, (None, Some(subgraph)));
675                            Ok(sub_rhs)
676                        }
677                    },
678                    (Some(_), Some(_), _) => panic!("Should never happen"),
679                }
680            };
681
682            match tokens_internal.len() {
683                0 => Ok(EdgeRhs {
684                    ..Default::default()
685                }),
686                _ => {
687                    match (
688                        tokens_internal.iter().position(|x| x == &edgeop),
689                        tokens_internal[1..].iter().position(|x| x == &edgeop),
690                    ) {
691                        (Some(0), None) => merge_and_return(
692                            parse_node_or_subgraph(&tokens_internal[1..]),
693                            tokens_internal.len(),
694                            &tokens_internal[0..0],
695                        ),
696                        (Some(0), Some(idx_next_edgeop)) => merge_and_return(
697                            parse_node_or_subgraph(&tokens_internal[1..idx_next_edgeop + 1]),
698                            idx_next_edgeop,
699                            &tokens_internal[idx_next_edgeop + 1..],
700                        ),
701                        (_, _) => Err((0, "edgeRHS should begin with edgeop")),
702                    }
703                }
704            }
705        };
706
707        match (tokens.len(), edgeop) {
708            (0, _) => Err((0, "edgeRHS expects non-empty token list")),
709            (_, "->") | (_, "--") => parse_internal(edgeop, tokens),
710            _ => Err((0, "edgeop should be '->'|'--'")),
711        }
712    }
713}
714
715pub struct EdgeStmt<'a> {
716    // It stores a sequence of node_id or subgraph.
717    node_id_or_subgraph: Vec<(Option<NodeId<'a>>, Option<SubGraph<'a>>)>,
718    attr_list: Option<AttrList<'a>>,
719}
720
721impl<'a> Parsable<'a> for EdgeStmt<'a> {
722    type Output = EdgeStmt<'a>;
723    fn parse_from(edgeop: &'a str, tokens: &[&'a str]) -> Result<Self::Output, (usize, &'a str)> {
724        let parse_edge = |idx_edge_rhs: usize,
725                          tokens_internal: &[&'a str]|
726         -> Result<EdgeStmt<'a>, (usize, &'a str)> {
727            match (
728                parse_node_or_subgraph(&tokens_internal[0..idx_edge_rhs]),
729                EdgeRhs::parse_from(edgeop, &tokens_internal[idx_edge_rhs..]),
730            ) {
731                ((None, None, (idx_err, err_msg)), _) => Err((idx_err, err_msg)),
732                (_, Err((idx_err, err_msg))) => Err((idx_err + idx_edge_rhs, err_msg)),
733                ((Some(_), Some(_), _), _) => panic!("Shouldn't happen"),
734                ((opt_node, opt_subgraph, _), Ok(mut edge_rhs)) => {
735                    edge_rhs
736                        .node_id_or_subgraph
737                        .insert(0, (opt_node, opt_subgraph));
738                    Ok(EdgeStmt {
739                        node_id_or_subgraph: edge_rhs.node_id_or_subgraph,
740                        attr_list: None,
741                    })
742                }
743            }
744        };
745
746        match (
747            tokens.iter().position(|x| x == &edgeop),
748            tokens.iter().position(|x| x == &"["),
749        ) {
750            (Some(idx_edge_rhs), Some(idx_attr_list)) => {
751                if idx_attr_list <= idx_edge_rhs {
752                    return Err((
753                        idx_attr_list,
754                        "Attr list should be at the end of statement.",
755                    ));
756                }
757                match (
758                    parse_edge(idx_edge_rhs, &tokens[0..idx_attr_list]),
759                    AttrList::parse_from(&tokens[idx_attr_list..]),
760                ) {
761                    (Err(err_info), _) => Err(err_info),
762                    (_, Err((idx_err, err_msg))) => Err((idx_err + idx_attr_list, err_msg)),
763                    (Ok(edge), Ok(attr_list)) => Ok(EdgeStmt {
764                        node_id_or_subgraph: edge.node_id_or_subgraph,
765                        attr_list: Some(attr_list),
766                    }),
767                }
768            }
769            (Some(idx_edge_rhs), None) => parse_edge(idx_edge_rhs, &tokens[0..]),
770            (None, Some(idx_attr_list)) => Err((idx_attr_list, "Expect edgeop")),
771            (None, None) => Err((tokens.len(), "Expect edgeop")),
772        }
773    }
774}
775
776pub struct Graph<'a> {
777    // TODO: apply strict limitation
778    // strict: bool,
779    kind: dot::Kind,
780    id: Option<IdWrapper<'a>>,
781    stmt_list: StmtList<'a>,
782}
783
784impl fmt::Debug for Graph<'_> {
785    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
786        let kind_str = match self.kind {
787            dot::Kind::Graph => "graph",
788            dot::Kind::Digraph => "digraph",
789        };
790        write!(
791            f,
792            "Graph{{
793    kind: {:?},
794    id: {:?},
795    stmt_list: {:?}
796}}",
797            kind_str, self.id, self.stmt_list
798        )
799    }
800}
801
802impl Graph<'_> {
803    pub fn parse_from<'a>(tokens: &[&'a str]) -> Option<Graph<'a>> {
804        if tokens.len() < 3 {
805            return None;
806        }
807        if tokens.last().unwrap() != &"}" {
808            return None;
809        }
810        if tokens[0] == "strict" {
811            return Graph::parse_from(&tokens[1..]);
812        }
813        let edgeop: &str = match tokens[0] {
814            "graph" => "--",
815            "digraph" => "->",
816            _ => return None,
817        };
818        let kind: dot::Kind = match tokens[0] {
819            "graph" => dot::Kind::Graph,
820            "digraph" => dot::Kind::Digraph,
821            _ => return None,
822        };
823        let mut id: Option<IdWrapper<'a>> = None;
824        let tokens_stmtlist = match (tokens[0], tokens[1]) {
825            ("{", _) => &tokens[1..tokens.len() - 1],
826            (id_str, "{") => {
827                match IdWrapper::new(id_str) {
828                    Ok(id_wrapper) => {
829                        id = Some(id_wrapper);
830                    }
831                    _ => {}
832                }
833                &tokens[2..tokens.len() - 1]
834            }
835            _ => return None,
836        };
837        match StmtList::parse_from(edgeop, tokens_stmtlist) {
838            Ok(stmtlist) => {
839                return Some(Graph {
840                    kind: kind,
841                    id: id,
842                    stmt_list: stmtlist,
843                })
844            }
845            Err(_) => return None,
846        }
847    }
848}
849
850#[cfg(test)]
851mod tests {
852    use super::*;
853
854    #[test]
855    fn format_print() {
856        assert_eq!(
857            format!(
858                "{:?}",
859                Port {
860                    id: Some(::dot::Id::new("id_1").unwrap()),
861                    ..Default::default()
862                }
863            ),
864            "Port{id=Some(\"id_1\"), compass=None}"
865        );
866        assert_eq!(
867            format!(
868                "{:?}",
869                Port {
870                    compass_pt: Some(CompassPt::NE),
871                    ..Default::default()
872                }
873            ),
874            "Port{id=None, compass=Some(\"NE\")}"
875        );
876        {
877            let mut alist = AList::new();
878            alist.0.insert(
879                std::borrow::Cow::Borrowed("a"),
880                IdWrapper::new("a1").unwrap(),
881            );
882            assert_eq!(format!("{:?}", alist), "{\"a\": \"a1\"}");
883        }
884        {
885            let tokens: Vec<&str> = "[ a = v1 ] [ b = v2 ] [ c = v3 ]"
886                .split_whitespace()
887                .collect();
888            let attr_list = AttrList::parse_from(&tokens).unwrap();
889            assert_eq!(
890                format!("{:?}", attr_list),
891                "[{\"c\": \"v3\"}, {\"b\": \"v2\"}, {\"a\": \"v1\"}]"
892            );
893        }
894    }
895
896    #[test]
897    fn parse_nodeid() {
898        let n1 = NodeId::parse_from(&["id1"]).unwrap();
899        assert_eq!(n1.id, "id1");
900        assert!(n1.port.is_none());
901
902        let n2 = NodeId::parse_from(&["id1", ":", "id2"]).unwrap();
903        assert_eq!(n2.id, "id1");
904        assert_eq!(n2.port.unwrap().id.unwrap().name(), "id2");
905
906        let n3 = NodeId::parse_from(&["id1", ":", "n"]).unwrap();
907        assert_eq!(n3.id, "id1");
908        assert!(matches!(n3.port.unwrap().compass_pt.unwrap(), CompassPt::N));
909
910        let n4 = NodeId::parse_from(&["id1", ":", "id2", ":", "c"]).unwrap();
911        assert_eq!(n4.id, "id1");
912        assert_eq!(
913            n4.port.unwrap(),
914            Port {
915                id: Some(::dot::Id::new("id2").unwrap()),
916                compass_pt: Some(CompassPt::C)
917            }
918        );
919    }
920
921    // Helper function to check if (key, value) exists in |alist|.
922    fn alist_entry_match(alist: &AList, key: &str, value: &str) -> bool {
923        alist.get(key).unwrap() == &value
924    }
925
926    #[test]
927    fn parse_alist() {
928        let alist_1 = AList::parse_from(&[]).unwrap();
929        assert_eq!(alist_1.len(), 0);
930
931        let alist_2 = AList::parse_from(&["id1", "=", "value1"]).unwrap();
932        assert_eq!(alist_2.len(), 1);
933        assert!(alist_entry_match(&alist_2, "id1", "value1"));
934
935        let alist_3 =
936            AList::parse_from(&["id1", "=", "value1", ";", "id2", "=", "value2"]).unwrap();
937        assert_eq!(alist_3.len(), 2);
938        assert!(alist_entry_match(&alist_3, "id1", "value1"));
939        assert!(alist_entry_match(&alist_3, "id2", "value2"));
940
941        let alist_4 =
942            AList::parse_from(&["id1", "=", "value1", "id2", "=", "value2", ","]).unwrap();
943        assert_eq!(alist_4.len(), 2);
944        assert!(alist_entry_match(&alist_4, "id1", "value1"));
945        assert!(alist_entry_match(&alist_4, "id2", "value2"));
946
947        let alist_5 = AList::parse_from(&["id1", "value1"]);
948        assert!(!alist_5.is_ok(), alist_5.unwrap());
949
950        let alist_6 = AList::parse_from(&["id1", "=", "value1", ":"]);
951        assert!(!alist_6.is_ok(), alist_6.unwrap());
952    }
953
954    #[test]
955    fn parse_attrlist() {
956        {
957            match AttrList::parse_from(&[]) {
958                Err((idx_err, err_msg)) => {
959                    assert_eq!(idx_err, 0, "{}", err_msg);
960                }
961                Ok(_) => {
962                    assert!(false, "cannot be empty");
963                }
964            }
965        }
966
967        {
968            match AttrList::parse_from(&["[", "id1", "=", "value1", "]"]) {
969                Err((idx_err, err_msg)) => {
970                    assert!(false, "error at index {}: {}", idx_err, err_msg);
971                }
972                Ok(attr_list) => {
973                    assert_eq!(attr_list.0.len(), 1);
974                    assert!(alist_entry_match(&attr_list.0[0], "id1", "value1"));
975                }
976            }
977        }
978
979        {
980            match AttrList::parse_from(&["[", "]", "[", "id1", "=", "value1", "]"]) {
981                Err((idx_err, err_msg)) => {
982                    assert!(false, "error at index {}: {}", idx_err, err_msg);
983                }
984                Ok(attr_list) => {
985                    assert_eq!(attr_list.0.len(), 2);
986                }
987            }
988        }
989
990        {
991            let attr_list = AttrList::parse_from(&["[", "]", ",", "[", "id1", "=", "value1", "]"]);
992            assert!(!attr_list.is_ok(), attr_list.unwrap());
993        }
994
995        {
996            let attr_list = AttrList::parse_from(&["[", "]", "[", "id1", "value1", "]"]);
997            assert!(!attr_list.is_ok(), attr_list.unwrap());
998        }
999    }
1000
1001    #[test]
1002    fn parse_node_stmt() {
1003        {
1004            let node_stmt = NodeStmt::parse_from("", &[]);
1005            assert!(!node_stmt.is_ok(), node_stmt.unwrap());
1006        }
1007
1008        {
1009            let tokens: Vec<&str> = "id1 : id2 : nw".split_whitespace().collect();
1010            let node_stmt = NodeStmt::parse_from("", tokens.as_slice()).unwrap();
1011            assert_eq!(node_stmt.id.id, "id1");
1012            assert_eq!(
1013                node_stmt.id.port.unwrap(),
1014                Port {
1015                    id: Some(::dot::Id::new("id2").unwrap()),
1016                    compass_pt: Some(CompassPt::NW)
1017                }
1018            )
1019        }
1020
1021        {
1022            let tokens: Vec<&str> = "id1 [ id2 = value2 ]".split_whitespace().collect();
1023            let node_stmt = NodeStmt::parse_from("", tokens.as_slice()).unwrap();
1024            assert_eq!(node_stmt.id.id, "id1");
1025            assert_eq!(node_stmt.attr_list.unwrap().0.len(), 1)
1026        }
1027
1028        {
1029            let tokens: Vec<&str> = "id1 : id2 : sw [ id3 = value3 ] [ id4 = value4 ]"
1030                .split_whitespace()
1031                .collect();
1032            let node_stmt = NodeStmt::parse_from("", tokens.as_slice()).unwrap();
1033            assert_eq!(node_stmt.id.id, "id1");
1034            assert_eq!(node_stmt.attr_list.unwrap().0.len(), 2)
1035        }
1036    }
1037
1038    #[test]
1039    fn parse_attr_stmt() {
1040        {
1041            let tokens: Vec<&str> = "[ ]".split_whitespace().collect();
1042            let node_stmt = AttrStmt::parse_from("", tokens.as_slice());
1043            assert!(!node_stmt.is_ok(), node_stmt.unwrap());
1044        }
1045
1046        {
1047            let tokens: Vec<&str> = "graph [ ]".split_whitespace().collect();
1048            let node_stmt = AttrStmt::parse_from("", tokens.as_slice()).unwrap();
1049            assert_eq!(node_stmt.key, AttrStmtKey::GRAPH);
1050        }
1051
1052        {
1053            let tokens: Vec<&str> = "edge".split_whitespace().collect();
1054            let node_stmt = AttrStmt::parse_from("", tokens.as_slice());
1055            assert!(!node_stmt.is_ok(), node_stmt.unwrap());
1056        }
1057
1058        {
1059            let tokens: Vec<&str> = "other_keyword []".split_whitespace().collect();
1060            let node_stmt = AttrStmt::parse_from("", tokens.as_slice());
1061            assert!(!node_stmt.is_ok(), node_stmt.unwrap());
1062        }
1063    }
1064
1065    #[test]
1066    fn parse_subgraph() {
1067        {
1068            let tokens: Vec<&str> = "{ }".split_whitespace().collect();
1069            let maybe_subgraph = SubGraph::parse_from("", tokens.as_slice());
1070            match maybe_subgraph {
1071                Ok(subgraph) => {
1072                    assert!(subgraph.id.is_none());
1073                }
1074                Err((idx_err, err_msg)) => {
1075                    assert!(false, format!("{} {}", idx_err, err_msg));
1076                }
1077            };
1078        }
1079
1080        {
1081            let tokens: Vec<&str> = "subgraph { }".split_whitespace().collect();
1082            let maybe_subgraph = SubGraph::parse_from("", tokens.as_slice());
1083            match maybe_subgraph {
1084                Ok(subgraph) => {
1085                    assert!(subgraph.id.is_none());
1086                }
1087                Err((idx_err, err_msg)) => {
1088                    assert!(false, format!("{} {}", idx_err, err_msg));
1089                }
1090            };
1091        }
1092
1093        {
1094            let tokens: Vec<&str> = "subgraph id1 { }".split_whitespace().collect();
1095            let maybe_subgraph = SubGraph::parse_from("", tokens.as_slice());
1096            match maybe_subgraph {
1097                Ok(subgraph) => {
1098                    assert!(subgraph.id.is_some());
1099                    assert_eq!(subgraph.id.unwrap().name(), "id1");
1100                }
1101                Err((idx_err, err_msg)) => {
1102                    assert!(false, format!("{} {}", idx_err, err_msg));
1103                }
1104            };
1105        }
1106
1107        {
1108            let tokens: Vec<&str> = "subgraph [ ]".split_whitespace().collect();
1109            let maybe_subgraph = SubGraph::parse_from("", tokens.as_slice());
1110            match maybe_subgraph {
1111                Ok(subgraph) => {
1112                    assert!(false, subgraph);
1113                }
1114                Err((idx_err, _)) => {
1115                    assert_eq!(idx_err, 0);
1116                }
1117            };
1118        }
1119
1120        {
1121            let tokens: Vec<&str> = "wrong_keyword [ ]".split_whitespace().collect();
1122            let maybe_subgraph = SubGraph::parse_from("", tokens.as_slice());
1123            match maybe_subgraph {
1124                Ok(subgraph) => {
1125                    assert!(false, subgraph);
1126                }
1127                Err((idx_err, _)) => {
1128                    assert_eq!(idx_err, 0);
1129                }
1130            };
1131        }
1132    }
1133
1134    #[test]
1135    fn parse_edge_rhs() {
1136        {
1137            let tokens: Vec<&str> = "-- id1".split_whitespace().collect();
1138            let maybe_edge_rhs = EdgeRhs::parse_from("--", tokens.as_slice());
1139            match maybe_edge_rhs {
1140                Ok(edge_rhs) => {
1141                    assert!(edge_rhs.node_id_or_subgraph.len() == 1);
1142                    assert!(edge_rhs.node_id_or_subgraph[0].1.is_none());
1143                }
1144                Err((idx_err, err_msg)) => {
1145                    assert!(false, format!("{} {}", idx_err, err_msg));
1146                }
1147            };
1148        }
1149
1150        {
1151            let tokens: Vec<&str> = "-> id1 -> id2 : id3 : n".split_whitespace().collect();
1152            let maybe_edge_rhs = EdgeRhs::parse_from("->", tokens.as_slice());
1153            match maybe_edge_rhs {
1154                Ok(edge_rhs) => {
1155                    assert!(edge_rhs.node_id_or_subgraph.len() == 2);
1156                    assert!(edge_rhs.node_id_or_subgraph[0].1.is_none());
1157                }
1158                Err((idx_err, err_msg)) => {
1159                    assert!(false, format!("{} {}", idx_err, err_msg));
1160                }
1161            };
1162        }
1163
1164        // TODO: add test for subgraph.
1165    }
1166
1167    #[test]
1168    fn parse_edge_stmt() {
1169        {
1170            let tokens: Vec<&str> = "id1 -- id2 -- id3 : id4 : n".split_whitespace().collect();
1171            let maybe_edge = EdgeStmt::parse_from("--", tokens.as_slice());
1172            match maybe_edge {
1173                Ok(edge) => {
1174                    assert!(edge.node_id_or_subgraph.len() == 3);
1175                    assert!(edge.node_id_or_subgraph[2].1.is_none());
1176                    assert_eq!(
1177                        edge.node_id_or_subgraph[2].0,
1178                        Some(NodeId {
1179                            id: IdWrapper::new("id3").unwrap(),
1180                            port: Some(Port {
1181                                id: Some(::dot::Id::new("id4").unwrap()),
1182                                compass_pt: Some(CompassPt::C)
1183                            })
1184                        })
1185                    );
1186                    assert!(edge.attr_list.is_none());
1187                }
1188                Err((idx_err, err_msg)) => {
1189                    assert!(false, format!("{} {}", idx_err, err_msg));
1190                }
1191            };
1192        }
1193
1194        {
1195            let tokens: Vec<&str> = "id1 -> id2 [ ]".split_whitespace().collect();
1196            let maybe_edge = EdgeStmt::parse_from("->", tokens.as_slice());
1197            match maybe_edge {
1198                Ok(edge) => {
1199                    assert!(edge.node_id_or_subgraph.len() == 2);
1200                    assert!(edge.attr_list.is_some());
1201                }
1202                Err((idx_err, err_msg)) => {
1203                    assert!(false, format!("{} {}", idx_err, err_msg));
1204                }
1205            };
1206        }
1207
1208        // TODO: test subgraph
1209    }
1210
1211    #[test]
1212    fn parse_stmt() {
1213        {
1214            let tokens: Vec<&str> = "id1 : id2".split_whitespace().collect();
1215            let maybe_stmt = Stmt::parse_from("--", tokens.as_slice());
1216            match maybe_stmt {
1217                Ok(stmt) => {
1218                    assert!(stmt.node_stmt.is_some());
1219                    assert_eq!(stmt.node_stmt.unwrap().id.id, "id1")
1220                }
1221                Err((idx_err, err_msg)) => {
1222                    assert!(false, format!("{} {}", idx_err, err_msg));
1223                }
1224            };
1225        }
1226
1227        {
1228            let tokens: Vec<&str> = "id1 -- id2 : id3".split_whitespace().collect();
1229            let maybe_stmt = Stmt::parse_from("--", tokens.as_slice());
1230            match maybe_stmt {
1231                Ok(stmt) => {
1232                    assert!(stmt.edge_stmt.is_some());
1233                    assert_eq!(stmt.edge_stmt.unwrap().node_id_or_subgraph.len(), 2);
1234                }
1235                Err((idx_err, err_msg)) => {
1236                    assert!(false, format!("{} {}", idx_err, err_msg));
1237                }
1238            };
1239        }
1240
1241        {
1242            let tokens: Vec<&str> = "graph [ ]".split_whitespace().collect();
1243            let maybe_stmt = Stmt::parse_from("--", tokens.as_slice());
1244            match maybe_stmt {
1245                Ok(stmt) => {
1246                    assert!(stmt.attr_stmt.is_some(), stmt);
1247                    assert_eq!(stmt.attr_stmt.unwrap().key, AttrStmtKey::GRAPH);
1248                }
1249                Err((idx_err, err_msg)) => {
1250                    assert!(false, format!("{} {}", idx_err, err_msg));
1251                }
1252            };
1253        }
1254
1255        {
1256            let tokens: Vec<&str> = "id1 = value1".split_whitespace().collect();
1257            let maybe_stmt = Stmt::parse_from("--", tokens.as_slice());
1258            match maybe_stmt {
1259                Ok(stmt) => {
1260                    assert!(stmt.assign_stmt.is_some(), stmt);
1261                    let assign_stmt = stmt.assign_stmt.unwrap();
1262                    assert_eq!(assign_stmt.lhs.0.as_slice(), "id1");
1263                    assert_eq!(assign_stmt.rhs.0.as_slice(), "value1");
1264                }
1265                Err((idx_err, err_msg)) => {
1266                    assert!(false, format!("{} {}", idx_err, err_msg));
1267                }
1268            };
1269        }
1270
1271        {
1272            let tokens: Vec<&str> = "subgraph { }".split_whitespace().collect();
1273            let maybe_stmt = Stmt::parse_from("--", tokens.as_slice());
1274            match maybe_stmt {
1275                Ok(stmt) => {
1276                    assert!(stmt.subgraph.is_some(), stmt);
1277                }
1278                Err((idx_err, err_msg)) => {
1279                    assert!(false, format!("{} {}", idx_err, err_msg));
1280                }
1281            };
1282        }
1283    }
1284
1285    #[test]
1286    fn parse_stmt_list() {
1287        {
1288            let tokens: Vec<&str> =
1289                "id1 : id2 ; id3 : id4 ; node1 [ ] ; node2 -- node3 ; subgraph { }"
1290                    .split_whitespace()
1291                    .collect();
1292            let maybe_stmtlist = StmtList::parse_from("--", tokens.as_slice());
1293            match maybe_stmtlist {
1294                Ok(stmtlist) => {
1295                    assert_eq!(stmtlist.0.len(), 5);
1296                }
1297                Err((idx_err, err_msg)) => {
1298                    assert!(false, format!("{} {}", idx_err, err_msg));
1299                }
1300            };
1301        }
1302    }
1303}
libdot_parse/lib.rs

libdot_parse/
lib.rs
