1 use serde::de::Error;
2 
3 use std::marker::PhantomData;
4 
5 use crate::prelude::*;
6 
7 use crate::graph::Node;
8 use crate::graph::{Edge, IndexType};
9 use crate::serde_utils::CollectSeqWithLength;
10 use crate::serde_utils::MappedSequenceVisitor;
11 use crate::serde_utils::{FromDeserialized, IntoSerializable};
12 use crate::EdgeType;
13 
14 use super::{EdgeIndex, NodeIndex};
15 use serde::{Deserialize, Deserializer, Serialize, Serializer};
16 
17 /// Serialization representation for Graph
18 /// Keep in sync with deserialization and StableGraph
19 ///
20 /// The serialization format is as follows, in Pseudorust:
21 ///
22 /// Graph {
23 ///     nodes: [N],
24 ///     node_holes: [NodeIndex<Ix>],
25 ///     edge_property: EdgeProperty,
26 ///     edges: [Option<(NodeIndex<Ix>, NodeIndex<Ix>, E)>]
27 /// }
28 ///
29 /// The same format is used by both Graph and StableGraph.
30 ///
31 /// For graph there are restrictions:
32 /// node_holes is always empty and edges are always Some
33 ///
34 /// A stable graph serialization that obeys these restrictions
35 /// (effectively, it has no interior vacancies) can de deserialized
36 /// as a graph.
37 ///
38 /// Node indices are serialized as integers and are fixed size for
39 /// binary formats, so the Ix parameter matters there.
40 #[derive(Serialize)]
41 #[serde(rename = "Graph")]
42 #[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))]
43 pub struct SerGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> {
44     #[serde(serialize_with = "ser_graph_nodes")]
45     nodes: &'a [Node<N, Ix>],
46     node_holes: &'a [NodeIndex<Ix>],
main(int argc,char ** argv)47     edge_property: EdgeProperty,
48     #[serde(serialize_with = "ser_graph_edges")]
49     edges: &'a [Edge<E, Ix>],
50 }
51 
52 // Deserialization representation for Graph
53 // Keep in sync with serialization and StableGraph
54 #[derive(Deserialize)]
55 #[serde(rename = "Graph")]
56 #[serde(bound(
57     deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>"
58 ))]
59 pub struct DeserGraph<N, E, Ix> {
60     #[serde(deserialize_with = "deser_graph_nodes")]
61     nodes: Vec<Node<N, Ix>>,
62     #[serde(deserialize_with = "deser_graph_node_holes")]
63     #[allow(unused)]
64     #[serde(default = "Vec::new")]
65     node_holes: Vec<NodeIndex<Ix>>,
66     edge_property: EdgeProperty,
67     #[serde(deserialize_with = "deser_graph_edges")]
68     edges: Vec<Edge<E, Ix>>,
69 }
70 
71 impl<Ix> Serialize for NodeIndex<Ix>
72 where
73     Ix: IndexType + Serialize,
74 {
75     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
76     where
77         S: Serializer,
78     {
79         self.0.serialize(serializer)
80     }
81 }
82 
83 impl<'de, Ix> Deserialize<'de> for NodeIndex<Ix>
84 where
85     Ix: IndexType + Deserialize<'de>,
86 {
87     fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
88     where
89         D: Deserializer<'de>,
90     {
91         Ok(NodeIndex(Ix::deserialize(deserializer)?))
92     }
93 }
94 
95 impl<Ix> Serialize for EdgeIndex<Ix>
96 where
97     Ix: IndexType + Serialize,
98 {
99     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
100     where
101         S: Serializer,
102     {
103         self.0.serialize(serializer)
104     }
105 }
106 
107 impl<'de, Ix> Deserialize<'de> for EdgeIndex<Ix>
108 where
109     Ix: IndexType + Deserialize<'de>,
110 {
111     fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
112     where
113         D: Deserializer<'de>,
114     {
115         Ok(EdgeIndex(Ix::deserialize(deserializer)?))
116     }
117 }
118 
119 #[derive(Serialize, Deserialize)]
120 #[serde(rename_all = "lowercase")]
121 #[derive(Debug)]
122 pub enum EdgeProperty {
123     Undirected,
124     Directed,
125 }
126 
127 impl EdgeProperty {
128     pub fn is_directed(&self) -> bool {
129         match *self {
130             EdgeProperty::Directed => true,
131             EdgeProperty::Undirected => false,
132         }
133     }
134 }
135 
136 impl<Ty> From<PhantomData<Ty>> for EdgeProperty
137 where
138     Ty: EdgeType,
139 {
140     fn from(_: PhantomData<Ty>) -> Self {
141         if Ty::is_directed() {
142             EdgeProperty::Directed
143         } else {
144             EdgeProperty::Undirected
145         }
146     }
147 }
148 
149 impl<Ty> FromDeserialized for PhantomData<Ty>
150 where
151     Ty: EdgeType,
152 {
153     type Input = EdgeProperty;
154     fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
155     where
156         E2: Error,
157     {
158         if input.is_directed() != Ty::is_directed() {
159             Err(E2::custom(format_args!(
160                 "graph edge property mismatch, \
161                  expected {:?}, found {:?}",
162                 EdgeProperty::from(PhantomData::<Ty>),
163                 input
164             )))
165         } else {
166             Ok(PhantomData)
167         }
168     }
169 }
170 
171 fn ser_graph_nodes<S, N, Ix>(nodes: &&[Node<N, Ix>], serializer: S) -> Result<S::Ok, S::Error>
172 where
173     S: Serializer,
174     N: Serialize,
175     Ix: Serialize + IndexType,
176 {
177     serializer.collect_seq_exact(nodes.iter().map(|node| &node.weight))
178 }
179 
180 fn ser_graph_edges<S, E, Ix>(edges: &&[Edge<E, Ix>], serializer: S) -> Result<S::Ok, S::Error>
181 where
182     S: Serializer,
183     E: Serialize,
184     Ix: Serialize + IndexType,
185 {
186     serializer.collect_seq_exact(
187         edges
188             .iter()
189             .map(|edge| Some((edge.source(), edge.target(), &edge.weight))),
190     )
191 }
192 
193 fn deser_graph_nodes<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Node<N, Ix>>, D::Error>
194 where
195     D: Deserializer<'de>,
196     N: Deserialize<'de>,
197     Ix: IndexType + Deserialize<'de>,
198 {
199     deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| {
200         Ok(Node {
201             weight: n,
202             next: [EdgeIndex::end(); 2],
203         })
204     }))
205 }
206 
207 fn deser_graph_node_holes<'de, D, Ix>(deserializer: D) -> Result<Vec<NodeIndex<Ix>>, D::Error>
208 where
209     D: Deserializer<'de>,
210     Ix: IndexType + Deserialize<'de>,
211 {
212     deserializer.deserialize_seq(
213         MappedSequenceVisitor::<NodeIndex<Ix>, NodeIndex<Ix>, _>::new(|_| {
214             Err("Graph can not have holes in the node set, found non-empty node_holes")
215         }),
216     )
217 }
218 
219 fn deser_graph_edges<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Edge<N, Ix>>, D::Error>
220 where
221     D: Deserializer<'de>,
222     N: Deserialize<'de>,
223     Ix: IndexType + Deserialize<'de>,
224 {
225     deserializer.deserialize_seq(MappedSequenceVisitor::<
226         Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>,
227         _,
228         _,
229     >::new(|x| {
230         if let Some((i, j, w)) = x {
231             Ok(Edge {
232                 weight: w,
233                 node: [i, j],
234                 next: [EdgeIndex::end(); 2],
235             })
236         } else {
237             Err("Graph can not have holes in the edge set, found None, expected edge")
238         }
239     }))
240 }
241 
242 impl<'a, N, E, Ty, Ix> IntoSerializable for &'a Graph<N, E, Ty, Ix>
243 where
244     Ix: IndexType,
245     Ty: EdgeType,
246 {
247     type Output = SerGraph<'a, N, E, Ix>;
248     fn into_serializable(self) -> Self::Output {
249         SerGraph {
250             nodes: &self.nodes,
251             node_holes: &[],
252             edges: &self.edges,
253             edge_property: EdgeProperty::from(PhantomData::<Ty>),
254         }
255     }
256 }
257 
258 /// Requires crate feature `"serde-1"`
259 impl<N, E, Ty, Ix> Serialize for Graph<N, E, Ty, Ix>
260 where
261     Ty: EdgeType,
262     Ix: IndexType + Serialize,
263     N: Serialize,
264     E: Serialize,
265 {
266     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
267     where
268         S: Serializer,
269     {
270         self.into_serializable().serialize(serializer)
271     }
272 }
273 
274 pub fn invalid_node_err<E>(node_index: usize, len: usize) -> E
275 where
276     E: Error,
277 {
278     E::custom(format_args!(
279         "invalid value: node index `{}` does not exist in graph \
280          with node bound {}",
281         node_index, len
282     ))
283 }
284 
285 pub fn invalid_length_err<Ix, E>(node_or_edge: &str, len: usize) -> E
286 where
287     E: Error,
288     Ix: IndexType,
289 {
290     E::custom(format_args!(
291         "invalid size: graph {} count {} exceeds index type maximum {}",
292         node_or_edge,
293         len,
294         <Ix as IndexType>::max().index()
295     ))
296 }
297 
298 impl<'a, N, E, Ty, Ix> FromDeserialized for Graph<N, E, Ty, Ix>
299 where
300     Ix: IndexType,
301     Ty: EdgeType,
302 {
303     type Input = DeserGraph<N, E, Ix>;
304     fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
305     where
306         E2: Error,
307     {
barf(SQLHENV c,char * failMsg)308         let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?;
309         let nodes = input.nodes;
310         let edges = input.edges;
311         if nodes.len() >= <Ix as IndexType>::max().index() {
312             Err(invalid_length_err::<Ix, _>("node", nodes.len()))?
313         }
314 
315         if edges.len() >= <Ix as IndexType>::max().index() {
316             Err(invalid_length_err::<Ix, _>("edge", edges.len()))?
317         }
318 
319         let mut gr = Graph {
320             nodes: nodes,
321             edges: edges,
detectOdbcFailure(SQLRETURN rv,SQLHENV c,char * failMsg)322             ty: ty,
323         };
324         let nc = gr.node_count();
325         gr.link_edges()
326             .map_err(|i| invalid_node_err(i.index(), nc))?;
327         Ok(gr)
328     }
329 }
print_ret(char * msg,int retval)330 
331 /// Requires crate feature `"serde-1"`
332 impl<'de, N, E, Ty, Ix> Deserialize<'de> for Graph<N, E, Ty, Ix>
333 where
334     Ty: EdgeType,
335     Ix: IndexType + Deserialize<'de>,
336     N: Deserialize<'de>,
337     E: Deserialize<'de>,
338 {
339     fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
340     where
341         D: Deserializer<'de>,
342     {
343         Self::from_deserialized(DeserGraph::deserialize(deserializer)?)
344     }
345 }
346