1use std::collections::HashSet;
8use std::path::Path;
9
10use quick_xml::Reader;
11use quick_xml::events::{BytesStart, Event};
12
13use crate::convert::{ConvertOptions, PageConsumer, read_limited_file};
14use crate::diagram::{DiagramEdge, DiagramGraph, DiagramNode, NodeShape, layout_and_render_graph};
15use crate::error::{Error, Result};
16
17const MAX_GRAPHML_BYTES: u64 = 64 * 1024 * 1024;
18const MAX_GRAPHML_EVENTS: usize = 1_000_000;
19const MAX_GRAPHML_DEPTH: usize = 128;
20const MAX_GRAPHML_NODES: usize = 100_000;
21const MAX_GRAPHML_EDGES: usize = 200_000;
22const MAX_GRAPHML_TEXT_BYTES: usize = 64 * 1024 * 1024;
23const MAX_GRAPHML_LABEL_BYTES: usize = 1024 * 1024;
24const MAX_GRAPHML_ID_BYTES: usize = 4096;
25
26pub(crate) fn looks_like_prefix(bytes: &[u8]) -> bool {
27 let text = String::from_utf8_lossy(bytes).to_ascii_lowercase();
28 text.contains("<graphml") && text.contains("<node")
29}
30
31pub(crate) fn convert(
32 path: &Path,
33 options: &ConvertOptions,
34 sink: &mut dyn PageConsumer,
35) -> Result<Vec<String>> {
36 let bytes = read_limited_file(
37 path,
38 options.max_input_bytes.min(MAX_GRAPHML_BYTES),
39 "GraphML input",
40 )?;
41 let text = std::str::from_utf8(&bytes)
42 .map_err(|error| Error::InvalidInput(format!("GraphML input must be UTF-8: {error}")))?;
43 let (mut graph, warnings) = parse_graphml(text)?;
44 graph.raw_source.clear();
45 let mut page = layout_and_render_graph(&graph, options)?;
46 page.source_format = "graphml".into();
47 page.title = graph
48 .title
49 .as_deref()
50 .filter(|title| !title.is_empty())
51 .map(|title| format!("GraphML — {title}"))
52 .unwrap_or_else(|| "GraphML graph".into());
53 page.description = format!(
54 "GraphML graph with {} nodes and {} edges",
55 graph.nodes.len(),
56 graph.edges.len()
57 );
58 for warning in &warnings {
59 page.warn(warning.clone());
60 }
61 sink.consume(page)?;
62 Ok(warnings)
63}
64
65struct NodeBuilder {
66 id: String,
67 label: String,
68 shape: NodeShape,
69}
70
71struct EdgeBuilder {
72 from: String,
73 to: String,
74 label: Option<String>,
75}
76
77#[derive(Default)]
78struct ParserState {
79 graph: DiagramGraph,
80 warnings: Vec<String>,
81 depth: usize,
82 events: usize,
83 text_bytes: usize,
84 node: Option<NodeBuilder>,
85 edge: Option<EdgeBuilder>,
86 capture: Option<CaptureTarget>,
87 seen_nodes: HashSet<String>,
88 seen_edges: usize,
89 nested_nodes: usize,
90 nested_node_depth: usize,
91 graph_seen: bool,
92 unsupported_graphs: usize,
93}
94
95enum CaptureTarget {
96 NodeLabel,
97 EdgeLabel,
98}
99
100fn parse_graphml(text: &str) -> Result<(DiagramGraph, Vec<String>)> {
101 if text.len() as u64 > MAX_GRAPHML_BYTES {
102 return Err(Error::LimitExceeded(format!(
103 "GraphML input exceeds {MAX_GRAPHML_BYTES} bytes"
104 )));
105 }
106 let mut reader = Reader::from_str(text);
107 reader.config_mut().trim_text(true);
108 let mut state = ParserState::default();
109 let mut root_seen = false;
110 loop {
111 state.events = state.events.saturating_add(1);
112 if state.events > MAX_GRAPHML_EVENTS {
113 return Err(Error::LimitExceeded(format!(
114 "GraphML exceeds {MAX_GRAPHML_EVENTS} XML events"
115 )));
116 }
117 match reader.read_event() {
118 Ok(Event::Start(start)) => {
119 let local = local_name(start.name().as_ref());
120 if !root_seen {
121 root_seen = true;
122 if local != "graphml" {
123 return Err(Error::InvalidInput(
124 "GraphML root element must be graphml".into(),
125 ));
126 }
127 }
128 state.depth = state.depth.saturating_add(1);
129 if state.depth > MAX_GRAPHML_DEPTH {
130 return Err(Error::LimitExceeded(format!(
131 "GraphML XML nesting exceeds {MAX_GRAPHML_DEPTH} levels"
132 )));
133 }
134 handle_start(&mut state, &start, &local)?;
135 }
136 Ok(Event::Empty(empty)) => {
137 state.events = state.events.saturating_add(1);
138 let local = local_name(empty.name().as_ref());
139 if !root_seen {
140 root_seen = true;
141 if local != "graphml" {
142 return Err(Error::InvalidInput(
143 "GraphML root element must be graphml".into(),
144 ));
145 }
146 }
147 handle_start(&mut state, &empty, &local)?;
148 handle_end(&mut state, &local)?;
149 }
150 Ok(Event::End(end)) => {
151 let local = local_name(end.name().as_ref());
152 handle_end(&mut state, &local)?;
153 state.depth = state.depth.saturating_sub(1);
154 }
155 Ok(Event::Text(text_event)) => {
156 let decoded = text_event.decode().map_err(|error| {
157 Error::InvalidInput(format!("invalid GraphML text: {error}"))
158 })?;
159 let value = quick_xml::escape::unescape(&decoded).map_err(|error| {
160 Error::InvalidInput(format!("invalid GraphML entity: {error}"))
161 })?;
162 append_capture(&mut state, value.as_ref())?;
163 }
164 Ok(Event::CData(cdata)) => {
165 let value = String::from_utf8_lossy(cdata.as_ref());
166 append_capture(&mut state, &value)?;
167 }
168 Ok(Event::DocType(_)) => {
169 return Err(Error::Unsupported(
170 "GraphML DTD and external entity declarations are unsupported".into(),
171 ));
172 }
173 Ok(Event::Eof) => break,
174 Ok(Event::Comment(_) | Event::Decl(_) | Event::PI(_) | Event::GeneralRef(_)) => {}
175 Err(error) => {
176 return Err(Error::InvalidInput(format!("invalid GraphML XML: {error}")));
177 }
178 }
179 }
180 if !root_seen {
181 return Err(Error::InvalidInput("GraphML input is empty".into()));
182 }
183 if state.node.is_some() || state.edge.is_some() {
184 return Err(Error::InvalidInput(
185 "GraphML input ended inside a node or edge".into(),
186 ));
187 }
188 if state.graph.nodes.is_empty() {
189 return Err(Error::InvalidInput("GraphML contains no nodes".into()));
190 }
191 if state.nested_nodes > 0 {
192 state.warnings.push(format!(
193 "GraphML omitted {0} nested node element(s); compound-node layout is not reconstructed",
194 state.nested_nodes
195 ));
196 }
197 if state.unsupported_graphs > 0 {
198 state.warnings.push(format!(
199 "GraphML omitted {0} nested graph element(s); only the first graph is rendered",
200 state.unsupported_graphs
201 ));
202 }
203 let known = state.seen_nodes;
204 let before = state.graph.edges.len();
205 state
206 .graph
207 .edges
208 .retain(|edge| known.contains(&edge.from) && known.contains(&edge.to));
209 let omitted_edges = before.saturating_sub(state.graph.edges.len());
210 if omitted_edges > 0 {
211 state.warnings.push(format!(
212 "GraphML omitted {omitted_edges} edge(s) referencing unknown nodes"
213 ));
214 }
215 Ok((state.graph, dedup_warnings(state.warnings)))
216}
217
218fn handle_start(state: &mut ParserState, start: &BytesStart<'_>, local: &str) -> Result<()> {
219 match local {
220 "graph" => {
221 if state.graph_seen {
222 state.unsupported_graphs = state.unsupported_graphs.saturating_add(1);
223 }
224 state.graph_seen = true;
225 state.graph.is_directed = true;
226 if let Some(default) = attr(start, "edgedefault") {
227 state.graph.is_directed = !default.eq_ignore_ascii_case("undirected");
228 }
229 if state.graph.title.is_none() {
230 state.graph.title = attr(start, "id");
231 }
232 }
233 "node" => {
234 if state.node.is_some() {
235 state.nested_nodes = state.nested_nodes.saturating_add(1);
236 state.nested_node_depth = state.nested_node_depth.saturating_add(1);
237 return Ok(());
238 }
239 if state.graph.nodes.len() >= MAX_GRAPHML_NODES {
240 return Err(Error::LimitExceeded(format!(
241 "GraphML exceeds {MAX_GRAPHML_NODES} nodes"
242 )));
243 }
244 let id = attr(start, "id").ok_or_else(|| {
245 Error::InvalidInput("GraphML node is missing its id attribute".into())
246 })?;
247 validate_id(&id, "node")?;
248 if !state.seen_nodes.insert(id.clone()) {
249 return Err(Error::InvalidInput(format!(
250 "GraphML node id '{id}' is duplicated"
251 )));
252 }
253 state.node = Some(NodeBuilder {
254 label: String::new(),
255 id,
256 shape: NodeShape::Box,
257 });
258 }
259 "edge" => {
260 if state.edge.is_some() {
261 return Ok(());
262 }
263 if state.seen_edges >= MAX_GRAPHML_EDGES {
264 return Err(Error::LimitExceeded(format!(
265 "GraphML exceeds {MAX_GRAPHML_EDGES} edges"
266 )));
267 }
268 let from = attr(start, "source").ok_or_else(|| {
269 Error::InvalidInput("GraphML edge is missing its source attribute".into())
270 })?;
271 let to = attr(start, "target").ok_or_else(|| {
272 Error::InvalidInput("GraphML edge is missing its target attribute".into())
273 })?;
274 validate_id(&from, "edge source")?;
275 validate_id(&to, "edge target")?;
276 if let Some(directed) = attr(start, "directed") {
277 let edge_is_directed =
278 matches!(directed.to_ascii_lowercase().as_str(), "true" | "1");
279 if edge_is_directed != state.graph.is_directed {
280 push_warning_once(
281 state,
282 "GraphML per-edge directed overrides were flattened to the graph default",
283 );
284 }
285 }
286 state.edge = Some(EdgeBuilder {
287 from,
288 to,
289 label: None,
290 });
291 state.seen_edges = state.seen_edges.saturating_add(1);
292 }
293 "nodelabel" => {
294 if state.node.is_some() && state.nested_node_depth == 0 {
295 if let Some(node) = state.node.as_mut() {
296 node.label.clear();
297 }
298 state.capture = Some(CaptureTarget::NodeLabel);
299 }
300 }
301 "label" => {
302 if state.edge.is_some() {
303 if let Some(edge) = state.edge.as_mut() {
304 edge.label = Some(String::new());
305 }
306 state.capture = Some(CaptureTarget::EdgeLabel);
307 }
308 }
309 "shape" => {
310 if state.nested_node_depth == 0
311 && let Some(node) = state.node.as_mut()
312 && let Some(shape) = attr(start, "type")
313 {
314 node.shape = match shape.to_ascii_lowercase().as_str() {
315 "ellipse" | "circle" => NodeShape::Circle,
316 "roundrectangle" | "roundedrectangle" | "rounded" => NodeShape::Rounded,
317 "diamond" => NodeShape::Diamond,
318 "cylinder" | "database" => NodeShape::Cylinder,
319 _ => NodeShape::Box,
320 };
321 }
322 }
323 "data" => {
324 if state
325 .node
326 .as_ref()
327 .is_some_and(|node| node.label.is_empty())
328 && state.nested_node_depth == 0
329 {
330 state.capture = Some(CaptureTarget::NodeLabel);
331 } else if state.edge.is_some() {
332 state.capture = Some(CaptureTarget::EdgeLabel);
333 }
334 }
335 _ => {}
336 }
337 Ok(())
338}
339
340fn handle_end(state: &mut ParserState, local: &str) -> Result<()> {
341 match local {
342 "nodelabel" | "label" | "data" => state.capture = None,
343 "node" => {
344 if state.nested_node_depth > 0 {
345 state.nested_node_depth = state.nested_node_depth.saturating_sub(1);
346 return Ok(());
347 }
348 if let Some(node) = state.node.take() {
349 state.graph.nodes.push(DiagramNode {
350 id: node.id,
351 label: if node.label.trim().is_empty() {
352 "node".into()
353 } else {
354 node.label.trim().to_string()
355 },
356 shape: node.shape,
357 x: 0.0,
358 y: 0.0,
359 width: 130.0,
360 height: 46.0,
361 });
362 }
363 }
364 "edge" => {
365 if let Some(edge) = state.edge.take() {
366 state.graph.edges.push(DiagramEdge {
367 from: edge.from,
368 to: edge.to,
369 label: edge.label.filter(|label| !label.trim().is_empty()),
370 });
371 }
372 }
373 _ => {}
374 }
375 Ok(())
376}
377
378fn append_capture(state: &mut ParserState, text: &str) -> Result<()> {
379 if state.capture.is_none() || text.is_empty() {
380 return Ok(());
381 }
382 state.text_bytes = state.text_bytes.saturating_add(text.len());
383 if state.text_bytes > MAX_GRAPHML_TEXT_BYTES {
384 return Err(Error::LimitExceeded(format!(
385 "GraphML text exceeds {MAX_GRAPHML_TEXT_BYTES} bytes"
386 )));
387 }
388 match state.capture {
389 Some(CaptureTarget::NodeLabel) => {
390 if let Some(node) = state.node.as_mut() {
391 append_label(&mut node.label, text)?;
392 }
393 }
394 Some(CaptureTarget::EdgeLabel) => {
395 if let Some(edge) = state.edge.as_mut() {
396 let label = edge.label.get_or_insert_with(String::new);
397 append_label(label, text)?;
398 }
399 }
400 None => {}
401 }
402 Ok(())
403}
404
405fn append_label(label: &mut String, text: &str) -> Result<()> {
406 if label.len().saturating_add(text.len()) > MAX_GRAPHML_LABEL_BYTES {
407 return Err(Error::LimitExceeded(format!(
408 "GraphML label exceeds {MAX_GRAPHML_LABEL_BYTES} bytes"
409 )));
410 }
411 label.push_str(text);
412 Ok(())
413}
414
415fn attr(start: &BytesStart<'_>, name: &str) -> Option<String> {
416 start
417 .attributes()
418 .flatten()
419 .find(|attribute| local_name(attribute.key.as_ref()).eq_ignore_ascii_case(name))
420 .and_then(|attribute| {
421 attribute
422 .decoded_and_normalized_value(quick_xml::XmlVersion::Implicit1_0, start.decoder())
423 .ok()
424 })
425 .map(|value| value.into_owned())
426}
427
428fn validate_id(id: &str, context: &str) -> Result<()> {
429 if id.is_empty() || id.len() > MAX_GRAPHML_ID_BYTES {
430 return Err(Error::InvalidInput(format!(
431 "GraphML {context} id is empty or exceeds {MAX_GRAPHML_ID_BYTES} bytes"
432 )));
433 }
434 Ok(())
435}
436
437fn local_name(bytes: &[u8]) -> String {
438 std::str::from_utf8(bytes)
439 .ok()
440 .and_then(|name| name.rsplit(':').next())
441 .unwrap_or_default()
442 .to_string()
443}
444
445fn dedup_warnings(mut warnings: Vec<String>) -> Vec<String> {
446 warnings.sort();
447 warnings.dedup();
448 warnings
449}
450
451fn push_warning_once(state: &mut ParserState, warning: &str) {
452 if !state.warnings.iter().any(|item| item == warning) {
453 state.warnings.push(warning.to_string());
454 }
455}
456
457#[cfg(test)]
458mod tests {
459 use super::{looks_like_prefix, parse_graphml};
460
461 #[test]
462 fn parses_nodes_edges_yfiles_labels_and_shapes() {
463 let source = r#"<?xml version="1.0"?>
464<graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:y="http://www.yworks.com/xml/graphml">
465 <graph id="workflow" edgedefault="directed">
466 <node id="start"><data key="d"><y:ShapeNode><y:NodeLabel>Start</y:NodeLabel><y:Shape type="ellipse"/></y:ShapeNode></data></node>
467 <node id="finish"><data key="d"><y:NodeLabel>Finish</y:NodeLabel></data></node>
468 <edge id="e1" source="start" target="finish"><data key="label">go</data></edge>
469 </graph>
470</graphml>"#;
471 let (graph, warnings) = parse_graphml(source).unwrap();
472 assert!(warnings.is_empty());
473 assert_eq!(graph.title.as_deref(), Some("workflow"));
474 assert_eq!(graph.nodes[0].label, "Start");
475 assert_eq!(graph.edges[0].label.as_deref(), Some("go"));
476 }
477
478 #[test]
479 fn requires_graphml_markers_for_sniffing() {
480 assert!(looks_like_prefix(
481 b"<graphml><graph><node id='a'/><edge source='a' target='a'/></graph></graphml>"
482 ));
483 assert!(!looks_like_prefix(b"<xml><node/><edge/></xml>"));
484 }
485
486 #[test]
487 fn rejects_dtds_before_external_processing() {
488 let source = "<!DOCTYPE graphml SYSTEM 'https://example.invalid/graphml.dtd'><graphml/>";
489 let error = parse_graphml(source).unwrap_err();
490 assert!(error.to_string().contains("DTD"));
491 }
492}