1use std::{error::Error, fmt};
2
3use rustc_hash::FxHashMap as HashMap;
4
5use crate::{
6 graph::{Graph, GraphMut, edge::Edge, node::Node, owning::OwningGraph},
7 registry::Identifier,
8};
9
10pub type TestGraph<'a> = OwningGraph<usize, usize, &'a str, &'a str>;
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum ParseErrorKind {
14 InvalidNodeDeclaration,
15 InvalidEdgeDeclaration,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub struct ParseError<'src> {
20 pub line_number: usize,
21 pub line: &'src str,
22 pub kind: ParseErrorKind,
23}
24
25impl fmt::Display for ParseError<'_> {
26 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27 match self.kind {
28 ParseErrorKind::InvalidNodeDeclaration => {
29 write!(f, "invalid node declaration on line {}", self.line_number)
30 }
31 ParseErrorKind::InvalidEdgeDeclaration => {
32 write!(f, "invalid edge declaration on line {}", self.line_number)
33 }
34 }
35 }
36}
37
38impl Error for ParseError<'_> {}
39
40impl<'src, NodeId: Identifier, EdgeId: Identifier>
41 OwningGraph<NodeId, EdgeId, &'src str, &'src str>
42{
43 pub fn parse(source: &'src str) -> Result<Self, ParseError<'src>> {
44 let mut graph = Self::default();
45 let mut node_ids: HashMap<&'src str, NodeId> = HashMap::default();
46
47 for (line_number, line) in source.lines().enumerate() {
48 let line_number = line_number + 1;
49 let trimmed = line.trim();
50
51 if trimmed.is_empty() {
52 continue;
53 }
54
55 if let Some((from_raw, to_raw)) = trimmed.split_once("->") {
56 let from_name = parse_identifier(from_raw).map_err(|_| ParseError {
57 line_number,
58 line,
59 kind: ParseErrorKind::InvalidEdgeDeclaration,
60 })?;
61
62 let (to_name, explicit_edge_data) =
63 parse_declaration(to_raw).map_err(|_| ParseError {
64 line_number,
65 line,
66 kind: ParseErrorKind::InvalidEdgeDeclaration,
67 })?;
68
69 let from_id = ensure_node(&mut graph, &mut node_ids, from_name, None);
70 let to_id = ensure_node(&mut graph, &mut node_ids, to_name, None);
71 let edge_data = explicit_edge_data.unwrap_or(trimmed);
72 graph.make_edge(from_id, to_id, edge_data);
73
74 continue;
75 }
76
77 let (name, explicit_node_data) =
78 parse_declaration(trimmed).map_err(|_| ParseError {
79 line_number,
80 line,
81 kind: ParseErrorKind::InvalidNodeDeclaration,
82 })?;
83
84 ensure_node(&mut graph, &mut node_ids, name, explicit_node_data);
85 }
86
87 Ok(graph)
88 }
89
90 pub fn get_node_by_name(&self, name: &str) -> Option<NodeId> {
91 self.nodes().find_map(|node| {
92 if *node.data() == name {
93 Some(node.id())
94 } else {
95 None
96 }
97 })
98 }
99
100 pub fn get_edge_by_data(&self, data: &str) -> Option<EdgeId> {
101 self.edges().find_map(|edge| {
102 if *edge.data() == data {
103 Some(edge.id())
104 } else {
105 None
106 }
107 })
108 }
109}
110
111fn ensure_node<'src, NodeId: Identifier, EdgeId: Identifier>(
112 graph: &mut OwningGraph<NodeId, EdgeId, &'src str, &'src str>,
113 node_ids: &mut HashMap<&'src str, NodeId>,
114 name: &'src str,
115 explicit_data: Option<&'src str>,
116) -> NodeId {
117 if let Some(&id) = node_ids.get(name) {
118 if let Some(data) = explicit_data {
119 *graph.get_node_mut(id).unwrap().data() = data;
120 }
121
122 return id;
123 }
124
125 let data = explicit_data.unwrap_or(name);
126 let id = graph.make_node(data);
127 node_ids.insert(name, id);
128 id
129}
130
131fn parse_identifier(input: &str) -> Result<&str, ()> {
132 let (name, payload) = parse_declaration(input)?;
133 if payload.is_some() {
134 return Err(());
135 }
136
137 Ok(name)
138}
139
140fn parse_declaration(input: &str) -> Result<(&str, Option<&str>), ()> {
141 let trimmed = input.trim();
142 if trimmed.is_empty() {
143 return Err(());
144 }
145
146 let split_index = trimmed
147 .find(|c: char| c.is_whitespace() || c == '[')
148 .unwrap_or(trimmed.len());
149
150 if split_index == 0 {
151 return Err(());
152 }
153
154 let name = &trimmed[..split_index];
155 let trailing = trimmed[split_index..].trim();
156
157 if trailing.is_empty() {
158 return Ok((name, None));
159 }
160
161 if !trailing.starts_with('[') || !trailing.ends_with(']') {
162 return Err(());
163 }
164
165 let payload = trailing[1..trailing.len() - 1].trim();
166 if payload.is_empty() {
167 return Err(());
168 }
169
170 Ok((name, Some(payload)))
171}
172
173#[cfg(test)]
174mod tests {
175 use crate::graph::{Graph, TestGraph};
176
177 #[test]
178 fn parse_supports_implicit_and_explicit_node_declarations() {
179 let source = "v0\nv1 [Hello World]\nv0 -> v1\nv1 -> v2 [Hello, World]";
180 let graph = TestGraph::parse(source).expect("parse should succeed");
181
182 assert_eq!(graph.nodes().count(), 3);
183 assert_eq!(graph.edges().count(), 2);
184
185 assert_eq!(*graph.get_node(0).unwrap().data(), "v0");
186 assert_eq!(*graph.get_node(1).unwrap().data(), "Hello World");
187 assert_eq!(*graph.get_node(2).unwrap().data(), "v2");
188
189 assert_eq!(*graph.get_edge(0).unwrap().data(), "v0 -> v1");
190 assert_eq!(*graph.get_edge(1).unwrap().data(), "Hello, World");
191 }
192
193 #[test]
194 fn parse_declares_missing_nodes_from_edge_declarations() {
195 let source = "a -> b";
196 let graph = TestGraph::parse(source).expect("parse should succeed");
197
198 assert_eq!(graph.nodes().count(), 2);
199 assert_eq!(*graph.get_node(0).unwrap().data(), "a");
200 assert_eq!(*graph.get_node(1).unwrap().data(), "b");
201 assert_eq!(graph.edges().count(), 1);
202 }
203
204 #[test]
205 fn parse_updates_existing_node_data_on_explicit_redeclaration() {
206 let source = "a -> b\nb [Bee]";
207 let graph = TestGraph::parse(source).expect("parse should succeed");
208
209 assert_eq!(graph.nodes().count(), 2);
210 assert_eq!(*graph.get_node(1).unwrap().data(), "Bee");
211 }
212
213 #[test]
214 fn parse_reports_invalid_declarations() {
215 let node_error = match TestGraph::parse("v0 [") {
216 Ok(_) => panic!("node declaration should fail"),
217 Err(error) => error,
218 };
219 assert_eq!(node_error.line_number, 1);
220 assert_eq!(node_error.to_string(), "invalid node declaration on line 1");
221
222 let edge_error = match TestGraph::parse("v0 -> [label]") {
223 Ok(_) => panic!("edge declaration should fail"),
224 Err(error) => error,
225 };
226 assert_eq!(edge_error.line_number, 1);
227 assert_eq!(edge_error.to_string(), "invalid edge declaration on line 1");
228 }
229
230 #[test]
231 fn lookup_helpers_find_parsed_items_and_skip_missing_ones() {
232 let graph = TestGraph::parse("\nalpha [Alpha]\nalpha -> beta [edge]\n")
233 .expect("parse should succeed");
234
235 let alpha = graph.get_node_by_name("Alpha").expect("node exists");
236 assert_eq!(*graph.get_node(alpha).unwrap().data(), "Alpha");
237 assert!(graph.get_node_by_name("missing").is_none());
238 let edge = graph.get_edge_by_data("edge").expect("edge exists");
239 assert_eq!(*graph.get_edge(edge).unwrap().data(), "edge");
240 assert!(graph.get_edge_by_data("missing").is_none());
241 }
242}