From 2aa4a82499d4becd2284cdb482213d541b8804dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 16:29:10 +0200 Subject: Adding upstream version 86.0.1. Signed-off-by: Daniel Baumann --- .../rust/petgraph/src/graph_impl/serialization.rs | 345 +++++++++++++++++++++ 1 file changed, 345 insertions(+) create mode 100644 third_party/rust/petgraph/src/graph_impl/serialization.rs (limited to 'third_party/rust/petgraph/src/graph_impl/serialization.rs') diff --git a/third_party/rust/petgraph/src/graph_impl/serialization.rs b/third_party/rust/petgraph/src/graph_impl/serialization.rs new file mode 100644 index 0000000000..e108f3dd47 --- /dev/null +++ b/third_party/rust/petgraph/src/graph_impl/serialization.rs @@ -0,0 +1,345 @@ +use serde::de::Error; + +use std::marker::PhantomData; + +use crate::prelude::*; + +use crate::graph::Node; +use crate::graph::{Edge, IndexType}; +use crate::serde_utils::CollectSeqWithLength; +use crate::serde_utils::MappedSequenceVisitor; +use crate::serde_utils::{FromDeserialized, IntoSerializable}; +use crate::EdgeType; + +use super::{EdgeIndex, NodeIndex}; +use serde::{Deserialize, Deserializer, Serialize, Serializer}; + +/// Serialization representation for Graph +/// Keep in sync with deserialization and StableGraph +/// +/// The serialization format is as follows, in Pseudorust: +/// +/// Graph { +/// nodes: [N], +/// node_holes: [NodeIndex], +/// edge_property: EdgeProperty, +/// edges: [Option<(NodeIndex, NodeIndex, E)>] +/// } +/// +/// The same format is used by both Graph and StableGraph. +/// +/// For graph there are restrictions: +/// node_holes is always empty and edges are always Some +/// +/// A stable graph serialization that obeys these restrictions +/// (effectively, it has no interior vacancies) can de deserialized +/// as a graph. +/// +/// Node indices are serialized as integers and are fixed size for +/// binary formats, so the Ix parameter matters there. +#[derive(Serialize)] +#[serde(rename = "Graph")] +#[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))] +pub struct SerGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> { + #[serde(serialize_with = "ser_graph_nodes")] + nodes: &'a [Node], + node_holes: &'a [NodeIndex], + edge_property: EdgeProperty, + #[serde(serialize_with = "ser_graph_edges")] + edges: &'a [Edge], +} + +// Deserialization representation for Graph +// Keep in sync with serialization and StableGraph +#[derive(Deserialize)] +#[serde(rename = "Graph")] +#[serde(bound( + deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>" +))] +pub struct DeserGraph { + #[serde(deserialize_with = "deser_graph_nodes")] + nodes: Vec>, + #[serde(deserialize_with = "deser_graph_node_holes")] + #[allow(unused)] + #[serde(default = "Vec::new")] + node_holes: Vec>, + edge_property: EdgeProperty, + #[serde(deserialize_with = "deser_graph_edges")] + edges: Vec>, +} + +impl Serialize for NodeIndex +where + Ix: IndexType + Serialize, +{ + fn serialize(&self, serializer: S) -> Result + where + S: Serializer, + { + self.0.serialize(serializer) + } +} + +impl<'de, Ix> Deserialize<'de> for NodeIndex +where + Ix: IndexType + Deserialize<'de>, +{ + fn deserialize(deserializer: D) -> Result + where + D: Deserializer<'de>, + { + Ok(NodeIndex(Ix::deserialize(deserializer)?)) + } +} + +impl Serialize for EdgeIndex +where + Ix: IndexType + Serialize, +{ + fn serialize(&self, serializer: S) -> Result + where + S: Serializer, + { + self.0.serialize(serializer) + } +} + +impl<'de, Ix> Deserialize<'de> for EdgeIndex +where + Ix: IndexType + Deserialize<'de>, +{ + fn deserialize(deserializer: D) -> Result + where + D: Deserializer<'de>, + { + Ok(EdgeIndex(Ix::deserialize(deserializer)?)) + } +} + +#[derive(Serialize, Deserialize)] +#[serde(rename_all = "lowercase")] +#[derive(Debug)] +pub enum EdgeProperty { + Undirected, + Directed, +} + +impl EdgeProperty { + pub fn is_directed(&self) -> bool { + match *self { + EdgeProperty::Directed => true, + EdgeProperty::Undirected => false, + } + } +} + +impl From> for EdgeProperty +where + Ty: EdgeType, +{ + fn from(_: PhantomData) -> Self { + if Ty::is_directed() { + EdgeProperty::Directed + } else { + EdgeProperty::Undirected + } + } +} + +impl FromDeserialized for PhantomData +where + Ty: EdgeType, +{ + type Input = EdgeProperty; + fn from_deserialized(input: Self::Input) -> Result + where + E2: Error, + { + if input.is_directed() != Ty::is_directed() { + Err(E2::custom(format_args!( + "graph edge property mismatch, \ + expected {:?}, found {:?}", + EdgeProperty::from(PhantomData::), + input + ))) + } else { + Ok(PhantomData) + } + } +} + +fn ser_graph_nodes(nodes: &&[Node], serializer: S) -> Result +where + S: Serializer, + N: Serialize, + Ix: Serialize + IndexType, +{ + serializer.collect_seq_exact(nodes.iter().map(|node| &node.weight)) +} + +fn ser_graph_edges(edges: &&[Edge], serializer: S) -> Result +where + S: Serializer, + E: Serialize, + Ix: Serialize + IndexType, +{ + serializer.collect_seq_exact( + edges + .iter() + .map(|edge| Some((edge.source(), edge.target(), &edge.weight))), + ) +} + +fn deser_graph_nodes<'de, D, N, Ix>(deserializer: D) -> Result>, D::Error> +where + D: Deserializer<'de>, + N: Deserialize<'de>, + Ix: IndexType + Deserialize<'de>, +{ + deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| { + Ok(Node { + weight: n, + next: [EdgeIndex::end(); 2], + }) + })) +} + +fn deser_graph_node_holes<'de, D, Ix>(deserializer: D) -> Result>, D::Error> +where + D: Deserializer<'de>, + Ix: IndexType + Deserialize<'de>, +{ + deserializer.deserialize_seq( + MappedSequenceVisitor::, NodeIndex, _>::new(|_| { + Err("Graph can not have holes in the node set, found non-empty node_holes") + }), + ) +} + +fn deser_graph_edges<'de, D, N, Ix>(deserializer: D) -> Result>, D::Error> +where + D: Deserializer<'de>, + N: Deserialize<'de>, + Ix: IndexType + Deserialize<'de>, +{ + deserializer.deserialize_seq(MappedSequenceVisitor::< + Option<(NodeIndex, NodeIndex, N)>, + _, + _, + >::new(|x| { + if let Some((i, j, w)) = x { + Ok(Edge { + weight: w, + node: [i, j], + next: [EdgeIndex::end(); 2], + }) + } else { + Err("Graph can not have holes in the edge set, found None, expected edge") + } + })) +} + +impl<'a, N, E, Ty, Ix> IntoSerializable for &'a Graph +where + Ix: IndexType, + Ty: EdgeType, +{ + type Output = SerGraph<'a, N, E, Ix>; + fn into_serializable(self) -> Self::Output { + SerGraph { + nodes: &self.nodes, + node_holes: &[], + edges: &self.edges, + edge_property: EdgeProperty::from(PhantomData::), + } + } +} + +/// Requires crate feature `"serde-1"` +impl Serialize for Graph +where + Ty: EdgeType, + Ix: IndexType + Serialize, + N: Serialize, + E: Serialize, +{ + fn serialize(&self, serializer: S) -> Result + where + S: Serializer, + { + self.into_serializable().serialize(serializer) + } +} + +pub fn invalid_node_err(node_index: usize, len: usize) -> E +where + E: Error, +{ + E::custom(format_args!( + "invalid value: node index `{}` does not exist in graph \ + with node bound {}", + node_index, len + )) +} + +pub fn invalid_length_err(node_or_edge: &str, len: usize) -> E +where + E: Error, + Ix: IndexType, +{ + E::custom(format_args!( + "invalid size: graph {} count {} exceeds index type maximum {}", + node_or_edge, + len, + ::max().index() + )) +} + +impl<'a, N, E, Ty, Ix> FromDeserialized for Graph +where + Ix: IndexType, + Ty: EdgeType, +{ + type Input = DeserGraph; + fn from_deserialized(input: Self::Input) -> Result + where + E2: Error, + { + let ty = PhantomData::::from_deserialized(input.edge_property)?; + let nodes = input.nodes; + let edges = input.edges; + if nodes.len() >= ::max().index() { + Err(invalid_length_err::("node", nodes.len()))? + } + + if edges.len() >= ::max().index() { + Err(invalid_length_err::("edge", edges.len()))? + } + + let mut gr = Graph { + nodes: nodes, + edges: edges, + ty: ty, + }; + let nc = gr.node_count(); + gr.link_edges() + .map_err(|i| invalid_node_err(i.index(), nc))?; + Ok(gr) + } +} + +/// Requires crate feature `"serde-1"` +impl<'de, N, E, Ty, Ix> Deserialize<'de> for Graph +where + Ty: EdgeType, + Ix: IndexType + Deserialize<'de>, + N: Deserialize<'de>, + E: Deserialize<'de>, +{ + fn deserialize(deserializer: D) -> Result + where + D: Deserializer<'de>, + { + Self::from_deserialized(DeserGraph::deserialize(deserializer)?) + } +} -- cgit v1.2.3