document_svg/document/
gml_graph.rs

1//! Bounded Graph Modeling Language (GML) graph preview.
2//!
3//! GML is a bracketed text graph format distinct from geographic GML XML.
4//! This adapter accepts the common `graph [ node [...] edge [...] ]` subset,
5//! preserving topology and labels while keeping arbitrary attributes inert.
6
7use std::collections::HashSet;
8use std::path::Path;
9
10use crate::convert::{ConvertOptions, PageConsumer, read_limited_file};
11use crate::diagram::{DiagramEdge, DiagramGraph, DiagramNode, NodeShape, layout_and_render_graph};
12use crate::error::{Error, Result};
13
14const MAX_GML_BYTES: u64 = 64 * 1024 * 1024;
15const MAX_GML_TOKENS: usize = 1_000_000;
16const MAX_GML_TOKEN_BYTES: usize = 4096;
17const MAX_GML_NODES: usize = 100_000;
18const MAX_GML_EDGES: usize = 200_000;
19const MAX_GML_LABEL_BYTES: usize = 1024 * 1024;
20const MAX_GML_ID_BYTES: usize = 4096;
21
22pub(crate) fn looks_like_prefix(bytes: &[u8]) -> bool {
23    let text = String::from_utf8_lossy(bytes);
24    let trimmed = text
25        .lines()
26        .map(str::trim)
27        .find(|line| !line.is_empty() && !line.starts_with('#'))
28        .unwrap_or_default();
29    trimmed.starts_with("graph")
30        && trimmed
31            .as_bytes()
32            .get(5)
33            .is_some_and(|byte| byte.is_ascii_whitespace() || *byte == b'[')
34        && trimmed.contains('[')
35        && text.contains("node")
36}
37
38pub(crate) fn convert(
39    path: &Path,
40    options: &ConvertOptions,
41    sink: &mut dyn PageConsumer,
42) -> Result<Vec<String>> {
43    let bytes = read_limited_file(
44        path,
45        options.max_input_bytes.min(MAX_GML_BYTES),
46        "Graph Modeling Language input",
47    )?;
48    let text = std::str::from_utf8(&bytes)
49        .map_err(|error| Error::InvalidInput(format!("Graph GML input must be UTF-8: {error}")))?;
50    let (graph, warnings) = parse_graph_gml(text)?;
51    let mut page = layout_and_render_graph(&graph, options)?;
52    page.source_format = "graph_gml".into();
53    page.title = graph
54        .title
55        .as_deref()
56        .filter(|title| !title.is_empty())
57        .map(|title| format!("Graph GML — {title}"))
58        .unwrap_or_else(|| "Graph Modeling Language graph".into());
59    page.description = format!(
60        "Graph Modeling Language graph with {} nodes and {} edges",
61        graph.nodes.len(),
62        graph.edges.len()
63    );
64    for warning in &warnings {
65        page.warn(warning.clone());
66    }
67    sink.consume(page)?;
68    Ok(warnings)
69}
70
71#[derive(Clone, Debug)]
72struct Tokenizer<'a> {
73    source: &'a str,
74    position: usize,
75}
76
77fn tokenize(source: &str) -> Result<Vec<String>> {
78    let mut tokenizer = Tokenizer {
79        source,
80        position: 0,
81    };
82    let mut tokens = Vec::new();
83    while let Some(token) = tokenizer.next_token()? {
84        if tokens.len() >= MAX_GML_TOKENS {
85            return Err(Error::LimitExceeded(format!(
86                "Graph GML exceeds {MAX_GML_TOKENS} tokens"
87            )));
88        }
89        tokens.push(token);
90    }
91    Ok(tokens)
92}
93
94impl<'a> Tokenizer<'a> {
95    fn next_token(&mut self) -> Result<Option<String>> {
96        let bytes = self.source.as_bytes();
97        while self.position < bytes.len() {
98            match bytes[self.position] {
99                b' ' | b'\t' | b'\r' | b'\n' => self.position += 1,
100                b'#' => {
101                    while self.position < bytes.len() && bytes[self.position] != b'\n' {
102                        self.position += 1;
103                    }
104                }
105                _ => break,
106            }
107        }
108        if self.position >= bytes.len() {
109            return Ok(None);
110        }
111        if matches!(bytes[self.position], b'[' | b']') {
112            let token = (bytes[self.position] as char).to_string();
113            self.position += 1;
114            return Ok(Some(token));
115        }
116        if bytes[self.position] == b'"' {
117            self.position += 1;
118            let mut value = String::new();
119            let mut escaped = false;
120            while self.position < bytes.len() {
121                let character = self.source[self.position..]
122                    .chars()
123                    .next()
124                    .unwrap_or_default();
125                self.position += character.len_utf8();
126                if escaped {
127                    value.push(match character {
128                        'n' => '\n',
129                        'r' => '\r',
130                        't' => '\t',
131                        other => other,
132                    });
133                    escaped = false;
134                } else if character == '\\' {
135                    escaped = true;
136                } else if character == '"' {
137                    if value.len() > MAX_GML_LABEL_BYTES {
138                        return Err(Error::LimitExceeded(format!(
139                            "Graph GML quoted value exceeds {MAX_GML_LABEL_BYTES} bytes"
140                        )));
141                    }
142                    return Ok(Some(value));
143                } else {
144                    value.push(character);
145                }
146            }
147            return Err(Error::InvalidInput(
148                "Graph GML quoted value is not closed".into(),
149            ));
150        }
151        let start = self.position;
152        while self.position < bytes.len()
153            && !bytes[self.position].is_ascii_whitespace()
154            && !matches!(bytes[self.position], b'[' | b']' | b'#')
155        {
156            self.position += 1;
157        }
158        let token = self.source.get(start..self.position).unwrap_or_default();
159        if token.is_empty() {
160            return Err(Error::InvalidInput(
161                "Graph GML contains an invalid token".into(),
162            ));
163        }
164        if token.len() > MAX_GML_TOKEN_BYTES {
165            return Err(Error::LimitExceeded(format!(
166                "Graph GML token exceeds {MAX_GML_TOKEN_BYTES} bytes"
167            )));
168        }
169        Ok(Some(token.to_string()))
170    }
171}
172
173fn parse_graph_gml(text: &str) -> Result<(DiagramGraph, Vec<String>)> {
174    if text.len() as u64 > MAX_GML_BYTES {
175        return Err(Error::LimitExceeded(format!(
176            "Graph GML input exceeds {MAX_GML_BYTES} bytes"
177        )));
178    }
179    let tokens = tokenize(text)?;
180    if tokens.len() < 2 || !tokens[0].eq_ignore_ascii_case("graph") || tokens[1] != "[" {
181        return Err(Error::InvalidInput(
182            "Graph GML must start with graph [".into(),
183        ));
184    }
185    let mut graph = DiagramGraph {
186        is_directed: false,
187        ..Default::default()
188    };
189    let mut warnings = Vec::new();
190    let mut seen_nodes = HashSet::new();
191    let mut edge_count = 0usize;
192    let mut index = 2usize;
193    while index < tokens.len() && tokens[index] != "]" {
194        let key = tokens[index].to_ascii_lowercase();
195        index += 1;
196        match key.as_str() {
197            "node" => {
198                let (node, next) = parse_node(&tokens, index, &mut warnings)?;
199                index = next;
200                if graph.nodes.len() >= MAX_GML_NODES {
201                    return Err(Error::LimitExceeded(format!(
202                        "Graph GML exceeds {MAX_GML_NODES} nodes"
203                    )));
204                }
205                if !seen_nodes.insert(node.id.clone()) {
206                    return Err(Error::InvalidInput(format!(
207                        "Graph GML node id '{}' is duplicated",
208                        node.id
209                    )));
210                }
211                graph.nodes.push(node);
212            }
213            "edge" => {
214                let (edge, next) = parse_edge(&tokens, index, &mut warnings)?;
215                index = next;
216                edge_count = edge_count.saturating_add(1);
217                if edge_count > MAX_GML_EDGES {
218                    return Err(Error::LimitExceeded(format!(
219                        "Graph GML exceeds {MAX_GML_EDGES} edges"
220                    )));
221                }
222                graph.edges.push(edge);
223            }
224            "directed" => {
225                let (value, next) = scalar(&tokens, index)?;
226                index = next;
227                graph.is_directed = matches!(value.trim(), "1" | "true" | "TRUE");
228            }
229            "label" => {
230                let (value, next) = scalar(&tokens, index)?;
231                index = next;
232                if value.len() > MAX_GML_LABEL_BYTES {
233                    return Err(Error::LimitExceeded(format!(
234                        "Graph GML label exceeds {MAX_GML_LABEL_BYTES} bytes"
235                    )));
236                }
237                graph.title = Some(value);
238            }
239            _ => {
240                let next = skip_value(&tokens, index)?;
241                index = next;
242                if key != "comment" {
243                    push_warning_once(
244                        &mut warnings,
245                        "Graph GML attributes other than node/edge labels and directed were omitted",
246                    );
247                }
248            }
249        }
250    }
251    if index >= tokens.len() || tokens[index] != "]" {
252        return Err(Error::InvalidInput(
253            "Graph GML graph container is not closed".into(),
254        ));
255    }
256    if index + 1 != tokens.len() {
257        return Err(Error::InvalidInput(
258            "Graph GML contains trailing tokens after the graph container".into(),
259        ));
260    }
261    if graph.nodes.is_empty() {
262        return Err(Error::InvalidInput("Graph GML contains no nodes".into()));
263    }
264    let before = graph.edges.len();
265    graph
266        .edges
267        .retain(|edge| seen_nodes.contains(&edge.from) && seen_nodes.contains(&edge.to));
268    if before != graph.edges.len() {
269        warnings.push(format!(
270            "Graph GML omitted {} edge(s) referencing unknown nodes",
271            before - graph.edges.len()
272        ));
273    }
274    warnings.sort();
275    warnings.dedup();
276    Ok((graph, warnings))
277}
278
279fn parse_node(
280    tokens: &[String],
281    start: usize,
282    warnings: &mut Vec<String>,
283) -> Result<(DiagramNode, usize)> {
284    let (fields, index) = fields(tokens, start)?;
285    let id = fields
286        .get("id")
287        .cloned()
288        .ok_or_else(|| Error::InvalidInput("Graph GML node is missing id".into()))?;
289    validate_id(&id, "node")?;
290    let label = fields.get("label").cloned().unwrap_or_else(|| id.clone());
291    if fields.contains_key("graphics") {
292        push_warning_once(
293            warnings,
294            "Graph GML node graphics and coordinates were omitted",
295        );
296    }
297    Ok((
298        DiagramNode {
299            id,
300            label,
301            shape: NodeShape::Box,
302            x: 0.0,
303            y: 0.0,
304            width: 130.0,
305            height: 46.0,
306        },
307        index,
308    ))
309}
310
311fn parse_edge(
312    tokens: &[String],
313    start: usize,
314    warnings: &mut Vec<String>,
315) -> Result<(DiagramEdge, usize)> {
316    let (fields, index) = fields(tokens, start)?;
317    let from = fields
318        .get("source")
319        .cloned()
320        .ok_or_else(|| Error::InvalidInput("Graph GML edge is missing source".into()))?;
321    let to = fields
322        .get("target")
323        .cloned()
324        .ok_or_else(|| Error::InvalidInput("Graph GML edge is missing target".into()))?;
325    validate_id(&from, "edge source")?;
326    validate_id(&to, "edge target")?;
327    if fields.contains_key("graphics") {
328        push_warning_once(
329            warnings,
330            "Graph GML edge graphics and coordinates were omitted",
331        );
332    }
333    Ok((
334        DiagramEdge {
335            from,
336            to,
337            label: fields.get("label").cloned(),
338        },
339        index,
340    ))
341}
342
343fn fields(
344    tokens: &[String],
345    start: usize,
346) -> Result<(std::collections::HashMap<String, String>, usize)> {
347    if tokens.get(start).map(String::as_str) != Some("[") {
348        return Err(Error::InvalidInput(
349            "Graph GML node/edge must contain a bracketed field list".into(),
350        ));
351    }
352    let mut fields = std::collections::HashMap::new();
353    let mut index = start + 1;
354    while index < tokens.len() && tokens[index] != "]" {
355        let key = tokens[index].to_ascii_lowercase();
356        index += 1;
357        if key == "node" || key == "edge" {
358            index = skip_value(tokens, index)?;
359            continue;
360        }
361        if tokens.get(index).map(String::as_str) == Some("[") {
362            if key == "graphics" {
363                fields.insert(key, "[graphics]".into());
364            }
365            index = skip_value(tokens, index)?;
366            continue;
367        }
368        let (value, next) = scalar(tokens, index)?;
369        index = next;
370        if key == "id" || key == "label" || key == "source" || key == "target" || key == "graphics"
371        {
372            fields.insert(key, value);
373        }
374    }
375    if index >= tokens.len() {
376        return Err(Error::InvalidInput(
377            "Graph GML node/edge container is not closed".into(),
378        ));
379    }
380    Ok((fields, index + 1))
381}
382
383fn scalar(tokens: &[String], start: usize) -> Result<(String, usize)> {
384    let value = tokens
385        .get(start)
386        .cloned()
387        .ok_or_else(|| Error::InvalidInput("Graph GML field is missing a value".into()))?;
388    if value == "[" || value == "]" {
389        return Err(Error::InvalidInput(
390            "Graph GML field value is not scalar".into(),
391        ));
392    }
393    Ok((value, start + 1))
394}
395
396fn skip_value(tokens: &[String], start: usize) -> Result<usize> {
397    if tokens.get(start).map(String::as_str) != Some("[") {
398        return Ok(start.saturating_add(1));
399    }
400    let mut depth = 0usize;
401    let mut index = start;
402    while index < tokens.len() {
403        match tokens[index].as_str() {
404            "[" => depth = depth.saturating_add(1),
405            "]" => {
406                depth = depth.saturating_sub(1);
407                if depth == 0 {
408                    return Ok(index + 1);
409                }
410            }
411            _ => {}
412        }
413        index += 1;
414    }
415    Err(Error::InvalidInput(
416        "Graph GML nested field container is not closed".into(),
417    ))
418}
419
420fn validate_id(id: &str, context: &str) -> Result<()> {
421    if id.is_empty() || id.len() > MAX_GML_ID_BYTES {
422        return Err(Error::InvalidInput(format!(
423            "Graph GML {context} id is empty or exceeds {MAX_GML_ID_BYTES} bytes"
424        )));
425    }
426    Ok(())
427}
428
429fn push_warning_once(warnings: &mut Vec<String>, warning: &str) {
430    if !warnings.iter().any(|item| item == warning) {
431        warnings.push(warning.to_string());
432    }
433}
434
435#[cfg(test)]
436mod tests {
437    use super::{looks_like_prefix, parse_graph_gml};
438
439    #[test]
440    fn parses_gml_graph_nodes_edges_and_comments() {
441        let source = r#"graph [
442          directed 1
443          label "Workflow"
444          node [ id 1 label "Start" graphics [ x 1 y 2 ] ]
445          node [ id 2 label "Done" ]
446          edge [ source 1 target 2 label "go" ]
447        ]"#;
448        let (graph, warnings) = parse_graph_gml(source).unwrap();
449        assert!(graph.is_directed);
450        assert_eq!(graph.title.as_deref(), Some("Workflow"));
451        assert_eq!(graph.nodes[0].label, "Start");
452        assert_eq!(graph.edges[0].label.as_deref(), Some("go"));
453        assert!(warnings.iter().any(|warning| warning.contains("graphics")));
454    }
455
456    #[test]
457    fn distinguishes_graph_gml_from_geographic_xml_gml() {
458        assert!(looks_like_prefix(b"graph [ node [ id 1 ] ]"));
459        assert!(looks_like_prefix(b"# comment\ngraph [ node [ id 1 ] ]"));
460        assert!(!looks_like_prefix(b"<gml><node/></gml>"));
461    }
462
463    #[test]
464    fn rejects_unclosed_quotes() {
465        let error = parse_graph_gml("graph [ node [ id 1 label \"bad ] ]").unwrap_err();
466        assert!(error.to_string().contains("quoted"));
467    }
468}
document_svg/document/gml_graph.rs

document_svg/document/
gml_graph.rs
