18639575611

Committed 20 Oct 2025 01:45AM UTC coverage: 94.186% (-0.01%) from 94.197%

Build # 18639575611

Build Type

Pull #1510

github

Committed by

web-flow

Commit Message

Merge 2a886a9aa into feda690dc

Pull Request Pull Request #1510: Bump MSRV to Rust 1.85, Edition to 2024, and PyO3 to 0.26

Coverage Stats

440 of 460 new or added lines in 41 files covered. (95.65%)

2 existing lines in 1 file now uncovered.

18272 of 19400 relevant lines covered (94.19%)

967619.47 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

72.12

/src/dot_parser/mod.rs

use pest::Parser;
use pest_derive::Parser;
use pyo3::prelude::*;
use pyo3::types::{PyDict, PyString};

use crate::StablePyGraph;
use crate::digraph::PyDiGraph;
use crate::graph::PyGraph;

use hashbrown::HashMap;
use rustworkx_core::petgraph::prelude::{Directed, NodeIndex, Undirected};

#[derive(Parser)]
#[grammar = "dot_parser/dot.pest"]
pub struct DotParser;

/// Keep a single graph value that can be either directed or undirected. This avoids generic return-type mismatches.
enum DotGraph {
    Directed(StablePyGraph<Directed>),
    Undirected(StablePyGraph<Undirected>),
}

impl DotGraph {
    fn new_directed() -> Self {
        DotGraph::Directed(StablePyGraph::<Directed>::with_capacity(0, 0))
    }
    fn new_undirected() -> Self {
        DotGraph::Undirected(StablePyGraph::<Undirected>::with_capacity(0, 0))
    }
    fn add_node(&mut self, w: Py<PyAny>) -> NodeIndex {
        match self {
            DotGraph::Directed(g) => g.add_node(w),
            DotGraph::Undirected(g) => g.add_node(w),
        }
    }
    fn add_edge(&mut self, a: NodeIndex, b: NodeIndex, w: Py<PyAny>) {
        match self {
            DotGraph::Directed(g) => {
                g.add_edge(a, b, w);
            }
            DotGraph::Undirected(g) => {
                g.add_edge(a, b, w);
            }
        }
    }

    #[allow(dead_code)]
    fn is_directed(&self) -> bool {
        matches!(self, DotGraph::Directed(_))
    }

    fn into_inner(self) -> Result<StablePyGraph<Directed>, StablePyGraph<Undirected>> {
        match self {
            DotGraph::Directed(g) => Ok(g),
            DotGraph::Undirected(g) => Err(g),
        }
    }
}

/// Unquote a quoted string
fn unquote_str(s: &str) -> String {
    let t = s.trim();
    if t.starts_with('"') && t.ends_with('"') && t.len() >= 2 {
        t[1..t.len() - 1]
            .replace("\\\"", "\"")
            .replace("\\\\", "\\")
    } else {
        t.to_string()
    }
}

/// Parse an `attr_list` pair into a Rust HashMap<String,String>
fn parse_attr_list_to_map(pair: pest::iterators::Pair<Rule>) -> HashMap<String, String> {
    let mut map = HashMap::new();
    for a_list in pair.into_inner() {
        if a_list.as_rule() != Rule::a_list {
            continue;
        }
        let tokens: Vec<_> = a_list.into_inner().collect();
        let mut i = 0usize;
        while i < tokens.len() {
            let key = tokens[i].as_str().trim().to_string();
            if i + 1 < tokens.len() {
                let val = tokens[i + 1].as_str().trim().to_string();
                map.insert(key, unquote_str(&val));
                i += 2;
            } else {
                map.insert(key, String::new());
                i += 1;
            }
        }
    }
    map
}

/// Extract the first inner token of node_id
fn node_id_to_string(pair: pest::iterators::Pair<Rule>) -> String {
    if let Some(child) = pair.into_inner().next() {
        return unquote_str(child.as_str().trim());
    }
    String::new()
}

#[pyfunction]
pub fn from_dot(py: Python<'_>, dot_str: &str) -> PyResult<Py<PyAny>> {
    let pairs = DotParser::parse(Rule::graph_file, dot_str).map_err(|e| {
        PyErr::new::<pyo3::exceptions::PyValueError, _>(format!("DOT parse error: {}", e))
    })?;

    // Detect directedness from a clone of the iterator so we don't consume it.
    let mut is_directed = false;
    for pair in pairs.clone() {
        if pair.as_rule() != Rule::graph_file {
            continue;
        }
        let mut inner = pair.into_inner();
        let first = inner.next().unwrap();
        let graph_type_str = if first.as_rule() == Rule::strict {
            inner.next().unwrap().as_str()
        } else {
            first.as_str()
        };
        is_directed = graph_type_str == "digraph";
        break;
    }

    build_graph_enum(py, pairs, is_directed)
}

fn build_graph_enum(
    py: Python<'_>,
    pairs: pest::iterators::Pairs<Rule>,
    is_directed: bool,
) -> PyResult<Py<PyAny>> {
    let mut node_map: HashMap<String, NodeIndex> = HashMap::new();
    let graph_attrs = PyDict::new(py);

    let mut default_node_attrs: HashMap<String, String> = HashMap::new();
    let mut default_edge_attrs: HashMap<String, String> = HashMap::new();

    let mut node_attrs_map: HashMap<String, Py<PyAny>> = HashMap::new();

    let mut graph = if is_directed {
        DotGraph::new_directed()
    } else {
        DotGraph::new_undirected()
    };

    for pair in pairs {
        if pair.as_rule() != Rule::graph_file {
            continue;
        }
        let mut inner = pair.into_inner();
        let first = inner.next().ok_or_else(|| {
            PyErr::new::<pyo3::exceptions::PyValueError, _>("Missing graph type in DOT")
        })?;
        if first.as_rule() == Rule::strict {
            inner.next();
        }

        for rest in inner {
            if rest.as_rule() != Rule::stmt_list {
                continue;
            }

            for stmt in rest.into_inner() {
                match stmt.as_rule() {
                    Rule::node_stmt => {
                        let mut it = stmt.into_inner();
                        let nid = it.next().ok_or_else(|| {
                            PyErr::new::<pyo3::exceptions::PyValueError, _>(
                                "Missing node id in DOT",
                            )
                        })?;
                        let name = node_id_to_string(nid);
                        let py_node_obj: Py<PyAny> = PyString::new(py, &name).into();

                        let idx = graph.add_node(py_node_obj);
                        node_map.insert(name.clone(), idx);

                        // Merge default node attrs + node's attr_list
                        let merged = PyDict::new(py);
                        for (k, v) in default_node_attrs.iter() {
                            merged.set_item(k.as_str(), v.as_str())?;
                        }
                        for maybe_attr in it {
                            if maybe_attr.as_rule() == Rule::attr_list {
                                let map = parse_attr_list_to_map(maybe_attr);
                                for (k, v) in map {
                                    merged.set_item(k.as_str(), v.as_str())?;
                                }
                            }
                        }
                        node_attrs_map.insert(name.clone(), merged.into());
                    }

                    Rule::edge_stmt => {
                        let mut endpoints: Vec<String> = Vec::new();

                        // Start collected edge attrs from defaults
                        let collected = PyDict::new(py);
                        for (k, v) in default_edge_attrs.iter() {
                            collected.set_item(k.as_str(), v.as_str())?;
                        }

                        for child in stmt.into_inner() {
                            match child.as_rule() {
                                Rule::edge_point => {
                                    for ep_child in child.into_inner() {
                                        if ep_child.as_rule() == Rule::node_id {
                                            let n = node_id_to_string(ep_child);
                                            endpoints.push(n);
                                        }
                                    }
                                }
                                Rule::edge_op => {
                                    // we already know directedness
                                }
                                Rule::attr_list => {
                                    let map = parse_attr_list_to_map(child);
                                    for (k, v) in map {
                                        collected.set_item(k.as_str(), v.as_str())?;
                                    }
                                }
                                _ => {}
                            }
                        }

                        // Pairwise edges along the chain
                        for i in 0..endpoints.len().saturating_sub(1) {
                            let src = endpoints[i].clone();
                            let dst = endpoints[i + 1].clone();

                            let src_idx = *node_map.entry(src.clone()).or_insert_with(|| {
                                let py_node: Py<PyAny> = PyString::new(py, &src).into();
                                graph.add_node(py_node)
                            });

                            let dst_idx = *node_map.entry(dst.clone()).or_insert_with(|| {
                                let py_node: Py<PyAny> = PyString::new(py, &dst).into();
                                graph.add_node(py_node)
                            });

                            let edge_attrs_obj: Py<PyAny> = collected.clone().into();
                            graph.add_edge(src_idx, dst_idx, edge_attrs_obj);
                        }
                    }

                    Rule::attr_stmt => {
                        // attr_stmt = ("graph" | "node" | "edge") ~ attr_list+
                        let mut it = stmt.into_inner();
                        if let Some(target_pair) = it.next() {
                            let target = target_pair.as_str();
                            for rest in it {
                                if rest.as_rule() == Rule::attr_list {
                                    let map = parse_attr_list_to_map(rest);
                                    match target {
                                        "graph" => {
                                            for (k, v) in map {
                                                graph_attrs.set_item(k.as_str(), v.as_str())?;
                                            }
                                        }
                                        "node" => {
                                            for (k, v) in map {
                                                default_node_attrs.insert(k, v);
                                            }
                                        }
                                        "edge" => {
                                            for (k, v) in map {
                                                default_edge_attrs.insert(k, v);
                                            }
                                        }
                                        _ => {}
                                    }
                                }
                            }
                        }
                    }

                    Rule::assignment => {
                        let mut parts = stmt.into_inner();
                        let key = parts.next().map(|p| p.as_str()).unwrap_or("");
                        let val = parts.next().map(|p| p.as_str()).unwrap_or("");
                        graph_attrs.set_item(key, val)?;
                    }

                    Rule::subgraph => {
                        return Err(PyErr::new::<pyo3::exceptions::PyNotImplementedError, _>(
                            "subgraph parsing is not supported",
                        ));
                    }

                    _ => {}
                }
            }
        }
    }

    // Wrap into the a Python class
    match graph.into_inner() {
        Ok(directed_graph) => {
            let dg = PyDiGraph {
                graph: directed_graph,
                cycle_state: rustworkx_core::petgraph::algo::DfsSpace::default(),
                check_cycle: false,
                node_removed: false,
                multigraph: true,
                attrs: graph_attrs.clone().into(),
            };
            Ok(Py::new(py, dg)?.into())
        }
        Err(undirected_graph) => {
            let ug = PyGraph {
                graph: undirected_graph,
                node_removed: false,
                multigraph: true,
                attrs: graph_attrs.clone().into(),
            };
            Ok(Py::new(py, ug)?.into())
        }
    }
}

1	use pest::Parser;
2	use pest_derive::Parser;
3	use pyo3::prelude::*;
4	use pyo3::types::{PyDict, PyString};
5
6	use crate::StablePyGraph;
7	use crate::digraph::PyDiGraph;
8	use crate::graph::PyGraph;
9
10	use hashbrown::HashMap;
11	use rustworkx_core::petgraph::prelude::{Directed, NodeIndex, Undirected};
12
13	#[derive(Parser)]
14	#[grammar = "dot_parser/dot.pest"]
15	pub struct DotParser;
16
17	/// Keep a single graph value that can be either directed or undirected. This avoids generic return-type mismatches.
18	enum DotGraph {
19	Directed(StablePyGraph<Directed>),
20	Undirected(StablePyGraph<Undirected>),
21	}
22
23	impl DotGraph {
24	fn new_directed() -> Self {	2✔
25	DotGraph::Directed(StablePyGraph::<Directed>::with_capacity(0, 0))	2✔
26	}	2✔
27	fn new_undirected() -> Self {	6✔
28	DotGraph::Undirected(StablePyGraph::<Undirected>::with_capacity(0, 0))	6✔
29	}	6✔
30	fn add_node(&mut self, w: Py<PyAny>) -> NodeIndex {	16✔
31	match self {	16✔
32	DotGraph::Directed(g) => g.add_node(w),	4✔
33	DotGraph::Undirected(g) => g.add_node(w),	12✔
34	}
35	}	16✔
36	fn add_edge(&mut self, a: NodeIndex, b: NodeIndex, w: Py<PyAny>) {	10✔
37	match self {	10✔
38	DotGraph::Directed(g) => {	2✔
39	g.add_edge(a, b, w);	2✔
40	}	2✔
41	DotGraph::Undirected(g) => {	8✔
42	g.add_edge(a, b, w);	8✔
43	}	8✔
44	}
45	}	10✔
46
47	#[allow(dead_code)]
48	fn is_directed(&self) -> bool {	×
49	matches!(self, DotGraph::Directed(_))	×
50	}	×
51
52	fn into_inner(self) -> Result<StablePyGraph<Directed>, StablePyGraph<Undirected>> {	8✔
53	match self {	8✔
54	DotGraph::Directed(g) => Ok(g),	2✔
55	DotGraph::Undirected(g) => Err(g),	6✔
56	}
57	}	8✔
58	}
59
60	/// Unquote a quoted string
61	fn unquote_str(s: &str) -> String {	120✔
62	let t = s.trim();	120✔
63	if t.starts_with('"') && t.ends_with('"') && t.len() >= 2 {	120✔
64	t[1..t.len() - 1]	26✔
65	.replace("\\\"", "\"")	26✔
66	.replace("\\\\", "\\")	26✔
67	} else {
68	t.to_string()	94✔
69	}
70	}	120✔
71
72	/// Parse an `attr_list` pair into a Rust HashMap<String,String>
73	fn parse_attr_list_to_map(pair: pest::iterators::Pair<Rule>) -> HashMap<String, String> {	26✔
74	let mut map = HashMap::new();	26✔
75	for a_list in pair.into_inner() {	26✔
76	if a_list.as_rule() != Rule::a_list {	26✔
77	continue;	×
78	}	26✔
79	let tokens: Vec<_> = a_list.into_inner().collect();	26✔
80	let mut i = 0usize;	26✔
81	while i < tokens.len() {	110✔
82	let key = tokens[i].as_str().trim().to_string();	84✔
83	if i + 1 < tokens.len() {	84✔
84	let val = tokens[i + 1].as_str().trim().to_string();	84✔
85	map.insert(key, unquote_str(&val));	84✔
86	i += 2;	84✔
87	} else {	84✔
88	map.insert(key, String::new());	×
89	i += 1;	×
90	}	×
91	}
92	}
93	map	26✔
94	}	26✔
95
96	/// Extract the first inner token of node_id
97	fn node_id_to_string(pair: pest::iterators::Pair<Rule>) -> String {	36✔
98	if let Some(child) = pair.into_inner().next() {	36✔
99	return unquote_str(child.as_str().trim());	36✔
100	}	×
101	String::new()	×
102	}	36✔
103
104	#[pyfunction]
105	pub fn from_dot(py: Python<'_>, dot_str: &str) -> PyResult<Py<PyAny>> {	8✔
106	let pairs = DotParser::parse(Rule::graph_file, dot_str).map_err(\|e\| {	8✔
107	PyErr::new::<pyo3::exceptions::PyValueError, _>(format!("DOT parse error: {}", e))	×
108	})?;	×
109
110	// Detect directedness from a clone of the iterator so we don't consume it.
111	let mut is_directed = false;	8✔
112	for pair in pairs.clone() {	8✔
113	if pair.as_rule() != Rule::graph_file {	8✔
114	continue;	×
115	}	8✔
116	let mut inner = pair.into_inner();	8✔
117	let first = inner.next().unwrap();	8✔
118	let graph_type_str = if first.as_rule() == Rule::strict {	8✔
119	inner.next().unwrap().as_str()	×
120	} else {
121	first.as_str()	8✔
122	};
123	is_directed = graph_type_str == "digraph";	8✔
124	break;	8✔
125	}
126
127	build_graph_enum(py, pairs, is_directed)	8✔
128	}	8✔
129
130	fn build_graph_enum(	8✔
131	py: Python<'_>,	8✔
132	pairs: pest::iterators::Pairs<Rule>,	8✔
133	is_directed: bool,	8✔
134	) -> PyResult<Py<PyAny>> {	8✔
135	let mut node_map: HashMap<String, NodeIndex> = HashMap::new();	8✔
136	let graph_attrs = PyDict::new(py);	8✔
137
138	let mut default_node_attrs: HashMap<String, String> = HashMap::new();	8✔
139	let mut default_edge_attrs: HashMap<String, String> = HashMap::new();	8✔
140
141	let mut node_attrs_map: HashMap<String, Py<PyAny>> = HashMap::new();	8✔
142
143	let mut graph = if is_directed {	8✔
144	DotGraph::new_directed()	2✔
145	} else {
146	DotGraph::new_undirected()	6✔
147	};
148
149	for pair in pairs {	16✔
150	if pair.as_rule() != Rule::graph_file {	8✔
151	continue;	×
152	}	8✔
153	let mut inner = pair.into_inner();	8✔
154	let first = inner.next().ok_or_else(\|\| {	8✔
155	PyErr::new::<pyo3::exceptions::PyValueError, _>("Missing graph type in DOT")	×
156	})?;	×
157	if first.as_rule() == Rule::strict {	8✔
158	inner.next();	×
159	}	8✔
160
161	for rest in inner {	24✔
162	if rest.as_rule() != Rule::stmt_list {	16✔
163	continue;	8✔
164	}	8✔
165
166	for stmt in rest.into_inner() {	26✔
167	match stmt.as_rule() {	26✔
168	Rule::node_stmt => {
169	let mut it = stmt.into_inner();	16✔
170	let nid = it.next().ok_or_else(\|\| {	16✔
171	PyErr::new::<pyo3::exceptions::PyValueError, _>(	×
172	"Missing node id in DOT",
173	)
174	})?;	×
175	let name = node_id_to_string(nid);	16✔
176	let py_node_obj: Py<PyAny> = PyString::new(py, &name).into();	16✔
177
178	let idx = graph.add_node(py_node_obj);	16✔
179	node_map.insert(name.clone(), idx);	16✔
180
181	// Merge default node attrs + node's attr_list
182	let merged = PyDict::new(py);	16✔
183	for (k, v) in default_node_attrs.iter() {	16✔
184	merged.set_item(k.as_str(), v.as_str())?;	×
185	}
186	for maybe_attr in it {	32✔
187	if maybe_attr.as_rule() == Rule::attr_list {	16✔
188	let map = parse_attr_list_to_map(maybe_attr);	16✔
189	for (k, v) in map {	80✔
190	merged.set_item(k.as_str(), v.as_str())?;	64✔
191	}
192	}	×
193	}
194	node_attrs_map.insert(name.clone(), merged.into());	16✔
195	}
196
197	Rule::edge_stmt => {
198	let mut endpoints: Vec<String> = Vec::new();	10✔
199
200	// Start collected edge attrs from defaults
201	let collected = PyDict::new(py);	10✔
202	for (k, v) in default_edge_attrs.iter() {	10✔
203	collected.set_item(k.as_str(), v.as_str())?;	×
204	}
205
206	for child in stmt.into_inner() {	40✔
207	match child.as_rule() {	40✔
208	Rule::edge_point => {
209	for ep_child in child.into_inner() {	20✔
210	if ep_child.as_rule() == Rule::node_id {	20✔
211	let n = node_id_to_string(ep_child);	20✔
212	endpoints.push(n);	20✔
213	}	20✔
214	}
215	}
216	Rule::edge_op => {	10✔
217	// we already know directedness	10✔
218	}	10✔
219	Rule::attr_list => {
220	let map = parse_attr_list_to_map(child);	10✔
221	for (k, v) in map {	30✔
222	collected.set_item(k.as_str(), v.as_str())?;	20✔
223	}
224	}
225	_ => {}	×
226	}
227	}
228
229	// Pairwise edges along the chain
230	for i in 0..endpoints.len().saturating_sub(1) {	10✔
231	let src = endpoints[i].clone();	10✔
232	let dst = endpoints[i + 1].clone();	10✔
233
234	let src_idx = *node_map.entry(src.clone()).or_insert_with(\|\| {	10✔
NEW 235	let py_node: Py<PyAny> = PyString::new(py, &src).into();	×
236	graph.add_node(py_node)	×
237	});	×
238
239	let dst_idx = *node_map.entry(dst.clone()).or_insert_with(\|\| {	10✔
NEW 240	let py_node: Py<PyAny> = PyString::new(py, &dst).into();	×
241	graph.add_node(py_node)	×
242	});	×
243
244	let edge_attrs_obj: Py<PyAny> = collected.clone().into();	10✔
245	graph.add_edge(src_idx, dst_idx, edge_attrs_obj);	10✔
246	}
247	}
248
249	Rule::attr_stmt => {
250	// attr_stmt = ("graph" \| "node" \| "edge") ~ attr_list+
251	let mut it = stmt.into_inner();	×
252	if let Some(target_pair) = it.next() {	×
253	let target = target_pair.as_str();	×
254	for rest in it {	×
255	if rest.as_rule() == Rule::attr_list {	×
256	let map = parse_attr_list_to_map(rest);	×
257	match target {	×
258	"graph" => {	×
259	for (k, v) in map {	×
260	graph_attrs.set_item(k.as_str(), v.as_str())?;	×
261	}
262	}
263	"node" => {	×
264	for (k, v) in map {	×
265	default_node_attrs.insert(k, v);	×
266	}	×
267	}
268	"edge" => {	×
269	for (k, v) in map {	×
270	default_edge_attrs.insert(k, v);	×
271	}	×
272	}
273	_ => {}	×
274	}
275	}	×
276	}
277	}	×
278	}
279
280	Rule::assignment => {
281	let mut parts = stmt.into_inner();	×
282	let key = parts.next().map(\|p\| p.as_str()).unwrap_or("");	×
283	let val = parts.next().map(\|p\| p.as_str()).unwrap_or("");	×
284	graph_attrs.set_item(key, val)?;	×
285	}
286
287	Rule::subgraph => {
288	return Err(PyErr::new::<pyo3::exceptions::PyNotImplementedError, _>(	×
289	"subgraph parsing is not supported",	×
290	));	×
291	}
292
293	_ => {}	×
294	}
295	}
296	}
297	}
298
299	// Wrap into the a Python class
300	match graph.into_inner() {	8✔
301	Ok(directed_graph) => {	2✔
302	let dg = PyDiGraph {	2✔
303	graph: directed_graph,	2✔
304	cycle_state: rustworkx_core::petgraph::algo::DfsSpace::default(),	2✔
305	check_cycle: false,	2✔
306	node_removed: false,	2✔
307	multigraph: true,	2✔
308	attrs: graph_attrs.clone().into(),	2✔
309	};	2✔
310	Ok(Py::new(py, dg)?.into())	2✔
311	}
312	Err(undirected_graph) => {	6✔
313	let ug = PyGraph {	6✔
314	graph: undirected_graph,	6✔
315	node_removed: false,	6✔
316	multigraph: true,	6✔
317	attrs: graph_attrs.clone().into(),	6✔
318	};	6✔
319	Ok(Py::new(py, ug)?.into())	6✔
320	}
321	}
322	}	8✔

Qiskit / rustworkx / 18639575611

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous