document_svg/document/
gexf.rs

1//! Bounded GEXF 1.3 graph preview.
2//!
3//! GEXF (Graph Exchange XML Format) is commonly emitted by Gephi. This
4//! adapter keeps the static node/edge topology and labels while leaving
5//! dynamic spells, attributes, layouts, plugins, and external resources inert.
6
7use 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_GEXF_BYTES: u64 = 64 * 1024 * 1024;
18const MAX_GEXF_EVENTS: usize = 1_000_000;
19const MAX_GEXF_DEPTH: usize = 128;
20const MAX_GEXF_NODES: usize = 100_000;
21const MAX_GEXF_EDGES: usize = 200_000;
22const MAX_GEXF_TEXT_BYTES: usize = 64 * 1024 * 1024;
23const MAX_GEXF_LABEL_BYTES: usize = 1024 * 1024;
24const MAX_GEXF_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("<gexf") && 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_GEXF_BYTES),
39        "GEXF input",
40    )?;
41    let text = std::str::from_utf8(&bytes)
42        .map_err(|error| Error::InvalidInput(format!("GEXF input must be UTF-8: {error}")))?;
43    let (graph, warnings) = parse_gexf(text)?;
44    let mut page = layout_and_render_graph(&graph, options)?;
45    page.source_format = "gexf".into();
46    page.title = graph
47        .title
48        .as_deref()
49        .filter(|title| !title.is_empty())
50        .map(|title| format!("GEXF — {title}"))
51        .unwrap_or_else(|| "GEXF graph".into());
52    page.description = format!(
53        "GEXF graph with {} nodes and {} edges",
54        graph.nodes.len(),
55        graph.edges.len()
56    );
57    for warning in &warnings {
58        page.warn(warning.clone());
59    }
60    sink.consume(page)?;
61    Ok(warnings)
62}
63
64struct NodeBuilder {
65    id: String,
66    label: String,
67}
68
69struct EdgeBuilder {
70    from: String,
71    to: String,
72    label: Option<String>,
73}
74
75#[derive(Default)]
76struct ParserState {
77    graph: DiagramGraph,
78    warnings: Vec<String>,
79    depth: usize,
80    events: usize,
81    text_bytes: usize,
82    node: Option<NodeBuilder>,
83    edge: Option<EdgeBuilder>,
84    capture: Option<CaptureTarget>,
85    seen_nodes: HashSet<String>,
86    seen_edges: usize,
87    nested_nodes: usize,
88    nested_node_depth: usize,
89    graph_seen: bool,
90    dynamic: bool,
91    attributes: bool,
92}
93
94enum CaptureTarget {
95    NodeLabel,
96    EdgeLabel,
97}
98
99fn parse_gexf(text: &str) -> Result<(DiagramGraph, Vec<String>)> {
100    if text.len() as u64 > MAX_GEXF_BYTES {
101        return Err(Error::LimitExceeded(format!(
102            "GEXF input exceeds {MAX_GEXF_BYTES} bytes"
103        )));
104    }
105    let mut reader = Reader::from_str(text);
106    reader.config_mut().trim_text(true);
107    let mut state = ParserState::default();
108    let mut root_seen = false;
109    loop {
110        state.events = state.events.saturating_add(1);
111        if state.events > MAX_GEXF_EVENTS {
112            return Err(Error::LimitExceeded(format!(
113                "GEXF exceeds {MAX_GEXF_EVENTS} XML events"
114            )));
115        }
116        match reader.read_event() {
117            Ok(Event::Start(start)) => {
118                let local = local_name(start.name().as_ref());
119                if !root_seen {
120                    root_seen = true;
121                    if local != "gexf" {
122                        return Err(Error::InvalidInput("GEXF root element must be gexf".into()));
123                    }
124                }
125                state.depth = state.depth.saturating_add(1);
126                if state.depth > MAX_GEXF_DEPTH {
127                    return Err(Error::LimitExceeded(format!(
128                        "GEXF XML nesting exceeds {MAX_GEXF_DEPTH} levels"
129                    )));
130                }
131                handle_start(&mut state, &start, &local)?;
132            }
133            Ok(Event::Empty(empty)) => {
134                state.events = state.events.saturating_add(1);
135                let local = local_name(empty.name().as_ref());
136                if !root_seen {
137                    root_seen = true;
138                    if local != "gexf" {
139                        return Err(Error::InvalidInput("GEXF root element must be gexf".into()));
140                    }
141                }
142                handle_start(&mut state, &empty, &local)?;
143                handle_end(&mut state, &local)?;
144            }
145            Ok(Event::End(end)) => {
146                let local = local_name(end.name().as_ref());
147                handle_end(&mut state, &local)?;
148                state.depth = state.depth.saturating_sub(1);
149            }
150            Ok(Event::Text(event)) => {
151                let decoded = event
152                    .decode()
153                    .map_err(|error| Error::InvalidInput(format!("invalid GEXF text: {error}")))?;
154                let value = quick_xml::escape::unescape(&decoded).map_err(|error| {
155                    Error::InvalidInput(format!("invalid GEXF entity: {error}"))
156                })?;
157                append_capture(&mut state, value.as_ref())?;
158            }
159            Ok(Event::CData(event)) => {
160                let value = event
161                    .decode()
162                    .map_err(|error| Error::InvalidInput(format!("invalid GEXF CDATA: {error}")))?;
163                append_capture(&mut state, value.as_ref())?;
164            }
165            Ok(Event::DocType(_)) => {
166                return Err(Error::Unsupported(
167                    "GEXF DTD and external entity declarations are unsupported".into(),
168                ));
169            }
170            Ok(Event::Eof) => break,
171            Ok(Event::Comment(_) | Event::Decl(_) | Event::PI(_) | Event::GeneralRef(_)) => {}
172            Err(error) => {
173                return Err(Error::InvalidInput(format!("invalid GEXF XML: {error}")));
174            }
175        }
176    }
177    if !root_seen {
178        return Err(Error::InvalidInput("GEXF input is empty".into()));
179    }
180    if state.node.is_some() || state.edge.is_some() {
181        return Err(Error::InvalidInput(
182            "GEXF input ended inside a node or edge".into(),
183        ));
184    }
185    if state.graph.nodes.is_empty() {
186        return Err(Error::InvalidInput("GEXF contains no nodes".into()));
187    }
188    if state.nested_nodes > 0 {
189        state.warnings.push(format!(
190            "GEXF omitted {} nested node element(s); compound-node layout is not reconstructed",
191            state.nested_nodes
192        ));
193    }
194    if state.dynamic {
195        state.warnings.push(
196            "GEXF dynamic spells/time attributes were omitted; the static topology is shown".into(),
197        );
198    }
199    if state.attributes {
200        state
201            .warnings
202            .push("GEXF node/edge attributes were omitted from the diagram labels".into());
203    }
204    let before = state.graph.edges.len();
205    state.graph.edges.retain(|edge| {
206        state.seen_nodes.contains(&edge.from) && state.seen_nodes.contains(&edge.to)
207    });
208    let omitted_edges = before.saturating_sub(state.graph.edges.len());
209    if omitted_edges > 0 {
210        state.warnings.push(format!(
211            "GEXF omitted {omitted_edges} edge(s) referencing unknown nodes"
212        ));
213    }
214    Ok((state.graph, dedup_warnings(state.warnings)))
215}
216
217fn handle_start(state: &mut ParserState, start: &BytesStart<'_>, local: &str) -> Result<()> {
218    match local {
219        "graph" => {
220            if state.graph_seen {
221                return Err(Error::Unsupported(
222                    "GEXF multiple graph elements are unsupported".into(),
223                ));
224            }
225            state.graph_seen = true;
226            state.graph.is_directed = true;
227            if let Some(edge_type) = attr(start, "defaultedgetype") {
228                state.graph.is_directed = !edge_type.eq_ignore_ascii_case("undirected");
229            }
230            state.graph.title = attr(start, "id");
231            if attr(start, "mode").is_some_and(|mode| mode.eq_ignore_ascii_case("dynamic")) {
232                state.dynamic = true;
233            }
234        }
235        "node" => {
236            if state.node.is_some() {
237                state.nested_nodes = state.nested_nodes.saturating_add(1);
238                state.nested_node_depth = state.nested_node_depth.saturating_add(1);
239                return Ok(());
240            }
241            if state.graph.nodes.len() >= MAX_GEXF_NODES {
242                return Err(Error::LimitExceeded(format!(
243                    "GEXF exceeds {MAX_GEXF_NODES} nodes"
244                )));
245            }
246            let id = attr(start, "id")
247                .ok_or_else(|| Error::InvalidInput("GEXF node is missing its id".into()))?;
248            validate_id(&id, "node")?;
249            if !state.seen_nodes.insert(id.clone()) {
250                return Err(Error::InvalidInput(format!(
251                    "GEXF node id '{id}' is duplicated"
252                )));
253            }
254            let label = attr(start, "label").unwrap_or_default();
255            if label.len() > MAX_GEXF_LABEL_BYTES {
256                return Err(Error::LimitExceeded(format!(
257                    "GEXF label exceeds {MAX_GEXF_LABEL_BYTES} bytes"
258                )));
259            }
260            state.node = Some(NodeBuilder { label, id });
261        }
262        "edge" => {
263            if state.edge.is_some() {
264                return Ok(());
265            }
266            if state.seen_edges >= MAX_GEXF_EDGES {
267                return Err(Error::LimitExceeded(format!(
268                    "GEXF exceeds {MAX_GEXF_EDGES} edges"
269                )));
270            }
271            let from = attr(start, "source")
272                .ok_or_else(|| Error::InvalidInput("GEXF edge is missing its source".into()))?;
273            let to = attr(start, "target")
274                .ok_or_else(|| Error::InvalidInput("GEXF edge is missing its target".into()))?;
275            validate_id(&from, "edge source")?;
276            validate_id(&to, "edge target")?;
277            let label = attr(start, "label");
278            if label
279                .as_ref()
280                .is_some_and(|value| value.len() > MAX_GEXF_LABEL_BYTES)
281            {
282                return Err(Error::LimitExceeded(format!(
283                    "GEXF label exceeds {MAX_GEXF_LABEL_BYTES} bytes"
284                )));
285            }
286            state.edge = Some(EdgeBuilder { from, to, label });
287            state.seen_edges = state.seen_edges.saturating_add(1);
288        }
289        "label" => {
290            if state.node.is_some() && state.nested_node_depth == 0 {
291                if let Some(node) = state.node.as_mut() {
292                    node.label.clear();
293                }
294                state.capture = Some(CaptureTarget::NodeLabel);
295            } else if state.edge.is_some() {
296                if let Some(edge) = state.edge.as_mut() {
297                    edge.label = Some(String::new());
298                }
299                state.capture = Some(CaptureTarget::EdgeLabel);
300            }
301        }
302        "attvalues" | "attvalue" | "attributes" | "spells" | "spell" => {
303            if matches!(local, "attvalues" | "attvalue" | "attributes") {
304                state.attributes = true;
305            }
306            if matches!(local, "spells" | "spell") {
307                state.dynamic = true;
308            }
309        }
310        _ => {}
311    }
312    Ok(())
313}
314
315fn handle_end(state: &mut ParserState, local: &str) -> Result<()> {
316    match local {
317        "label" => state.capture = None,
318        "node" => {
319            if state.nested_node_depth > 0 {
320                state.nested_node_depth = state.nested_node_depth.saturating_sub(1);
321                return Ok(());
322            }
323            if let Some(node) = state.node.take() {
324                state.graph.nodes.push(DiagramNode {
325                    id: node.id,
326                    label: if node.label.trim().is_empty() {
327                        "node".into()
328                    } else {
329                        node.label.trim().to_string()
330                    },
331                    shape: NodeShape::Box,
332                    x: 0.0,
333                    y: 0.0,
334                    width: 130.0,
335                    height: 46.0,
336                });
337            }
338        }
339        "edge" => {
340            if let Some(edge) = state.edge.take() {
341                state.graph.edges.push(DiagramEdge {
342                    from: edge.from,
343                    to: edge.to,
344                    label: edge.label.filter(|label| !label.trim().is_empty()),
345                });
346            }
347        }
348        _ => {}
349    }
350    Ok(())
351}
352
353fn append_capture(state: &mut ParserState, text: &str) -> Result<()> {
354    if state.capture.is_none() || text.is_empty() {
355        return Ok(());
356    }
357    state.text_bytes = state.text_bytes.saturating_add(text.len());
358    if state.text_bytes > MAX_GEXF_TEXT_BYTES {
359        return Err(Error::LimitExceeded(format!(
360            "GEXF text exceeds {MAX_GEXF_TEXT_BYTES} bytes"
361        )));
362    }
363    match state.capture {
364        Some(CaptureTarget::NodeLabel) => {
365            if let Some(node) = state.node.as_mut() {
366                append_label(&mut node.label, text)?;
367            }
368        }
369        Some(CaptureTarget::EdgeLabel) => {
370            if let Some(edge) = state.edge.as_mut() {
371                let label = edge.label.get_or_insert_with(String::new);
372                append_label(label, text)?;
373            }
374        }
375        None => {}
376    }
377    Ok(())
378}
379
380fn append_label(label: &mut String, text: &str) -> Result<()> {
381    if label.len().saturating_add(text.len()) > MAX_GEXF_LABEL_BYTES {
382        return Err(Error::LimitExceeded(format!(
383            "GEXF label exceeds {MAX_GEXF_LABEL_BYTES} bytes"
384        )));
385    }
386    label.push_str(text);
387    Ok(())
388}
389
390fn attr(start: &BytesStart<'_>, name: &str) -> Option<String> {
391    start
392        .attributes()
393        .flatten()
394        .find(|attribute| local_name(attribute.key.as_ref()).eq_ignore_ascii_case(name))
395        .and_then(|attribute| {
396            attribute
397                .decoded_and_normalized_value(quick_xml::XmlVersion::Implicit1_0, start.decoder())
398                .ok()
399        })
400        .map(|value| value.into_owned())
401}
402
403fn validate_id(id: &str, context: &str) -> Result<()> {
404    if id.is_empty() || id.len() > MAX_GEXF_ID_BYTES {
405        return Err(Error::InvalidInput(format!(
406            "GEXF {context} id is empty or exceeds {MAX_GEXF_ID_BYTES} bytes"
407        )));
408    }
409    Ok(())
410}
411
412fn local_name(bytes: &[u8]) -> String {
413    std::str::from_utf8(bytes)
414        .ok()
415        .and_then(|name| name.rsplit(':').next())
416        .unwrap_or_default()
417        .to_string()
418}
419
420fn dedup_warnings(mut warnings: Vec<String>) -> Vec<String> {
421    warnings.sort();
422    warnings.dedup();
423    warnings
424}
425
426#[cfg(test)]
427mod tests {
428    use super::{looks_like_prefix, parse_gexf};
429
430    #[test]
431    fn parses_static_gexf_nodes_edges_and_labels() {
432        let source = r#"<?xml version="1.0"?>
433<gexf xmlns="http://gexf.net/1.3" version="1.3">
434  <graph mode="static" defaultedgetype="directed" id="workflow">
435    <nodes><node id="a" label="Start"/><node id="b"><label>Done</label></node></nodes>
436    <edges><edge id="e" source="a" target="b" label="approve"/></edges>
437  </graph>
438</gexf>"#;
439        let (graph, warnings) = parse_gexf(source).unwrap();
440        assert!(warnings.is_empty());
441        assert_eq!(graph.title.as_deref(), Some("workflow"));
442        assert_eq!(graph.nodes[0].label, "Start");
443        assert_eq!(graph.nodes[1].label, "Done");
444        assert_eq!(graph.edges[0].label.as_deref(), Some("approve"));
445    }
446
447    #[test]
448    fn recognizes_gexf_without_confusing_generic_xml() {
449        assert!(looks_like_prefix(
450            b"<gexf><graph><nodes><node id='a'/></nodes></graph></gexf>"
451        ));
452        assert!(!looks_like_prefix(b"<graphml><node id='a'/></graphml>"));
453    }
454
455    #[test]
456    fn rejects_dtd_before_external_processing() {
457        let source = "<!DOCTYPE gexf SYSTEM 'https://example.invalid/gexf.dtd'><gexf/>";
458        let error = parse_gexf(source).unwrap_err();
459        assert!(error.to_string().contains("DTD"));
460    }
461}
document_svg/document/gexf.rs

document_svg/document/
gexf.rs
