Skip to main content

deduxit/serialize/
nets.rs

1// deduxit © Fabian Lukas Grubmüller 2026
2// Licensed under the EUPL
3
4use super::sequents::Sequent;
5use crate::limits::Limits;
6use crate::linear::fragment::Order;
7use crate::linear::nets::{Criterion, MellStructure, Parts, Placed, ProofStructure, VertexId};
8use crate::linear::occurrences::{Forest, OccId};
9use crate::wire::{self, Readable};
10use serde::{Deserialize, Deserializer, Serialize, Serializer};
11
12/// The serialized form of a proof structure: its level, its sequent, the
13/// criterion's fields, its cut links where it has some, and its axiom
14/// links in the order they were made. The criterion's fields are whether
15/// Mix is allowed, and the order where it is not the commutative one. A
16/// link is a pair of vertex ids.
17#[derive(Clone, Debug, Serialize, Deserialize)]
18struct Net {
19    /// The wire level.
20    #[serde(
21        default,
22        skip_serializing_if = "Option::is_none",
23        deserialize_with = "wire::version"
24    )]
25    version: Option<u32>,
26    /// The sequent.
27    sequent: Sequent,
28    /// Whether Mix is allowed.
29    mix: bool,
30    /// The order the criterion keeps, written where it is not the
31    /// commutative one.
32    #[serde(default, skip_serializing_if = "Option::is_none")]
33    order: Option<OrderForm>,
34    /// The cut links, written where there are some.
35    #[serde(default, skip_serializing_if = "Vec::is_empty")]
36    cuts: Vec<(u32, u32)>,
37    /// The axiom links.
38    links: Vec<(u32, u32)>,
39    /// The vertices of a structure with boxes. This form refuses them,
40    /// since the links of such a structure name its vertices, not
41    /// occurrences.
42    #[serde(default, skip_serializing)]
43    vertices: Option<serde::de::IgnoredAny>,
44}
45
46/// An order other than the commutative one, by its name.
47#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
48#[serde(rename_all = "lowercase")]
49enum OrderForm {
50    /// The commutative order, which a writer leaves out.
51    Commutative,
52    /// The cyclic order.
53    Cyclic,
54}
55
56impl From<OrderForm> for Order {
57    /// Returns the order the name names.
58    fn from(form: OrderForm) -> Self {
59        match form {
60            OrderForm::Commutative => Order::Commutative,
61            OrderForm::Cyclic => Order::Cyclic,
62        }
63    }
64}
65
66impl Serialize for ProofStructure {
67    /// Serializes the structure as a document: its level, sequent,
68    /// criterion, cut links and links.
69    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
70        form(self).serialize(serializer)
71    }
72}
73
74/// Returns the form of a proof structure, with its level.
75fn form(net: &ProofStructure) -> Net {
76    let order = match net.criterion().order {
77        Order::Commutative => None,
78        Order::Cyclic => Some(OrderForm::Cyclic),
79    };
80    let pair = |&(x, y): &(VertexId, VertexId)| (x.get(), y.get());
81    Net {
82        // The cyclic order needs level 2. The sequent's own level is 6
83        // with cut formulas and 7 when it is first-order.
84        version: Some(if order.is_some() {
85            wire::level_of_sequent(net.sequent()).max(2)
86        } else {
87            wire::level_of_sequent(net.sequent())
88        }),
89        sequent: Sequent::from(net.sequent()),
90        mix: net.criterion().mix,
91        order,
92        vertices: None,
93        cuts: net.cuts().iter().map(pair).collect(),
94        links: net.links().iter().map(pair).collect(),
95    }
96}
97
98impl<'a> Deserialize<'a> for ProofStructure {
99    /// Deserializes a structure within the default limits, as
100    /// [`wire::upgrade`] does.
101    fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error> {
102        Self::read(deserializer, &Limits::default())
103    }
104}
105
106impl crate::sealed::Readable for ProofStructure {}
107
108impl Readable for ProofStructure {
109    const FORM: &'static str = "proof structure";
110
111    /// Reads a structure. Builds the forest of its sequent within the
112    /// limits, and validates the cut links and links as
113    /// [`ProofStructure::with_cuts`] does. Whether it is a proof net is
114    /// for [`ProofStructure::is_correct`] to say.
115    fn read<'de, D: Deserializer<'de>>(deserializer: D, limits: &Limits) -> Result<Self, D::Error> {
116        let net = Net::deserialize(deserializer)?;
117        if net.vertices.is_some() {
118            return Err(serde::de::Error::custom(
119                "a proof structure with boxes, whose links name its vertices: read it as one",
120            ));
121        }
122        let build = || {
123            let sequent = crate::linear::Sequent::try_from(net.sequent)?;
124            let forest = Forest::from_owned(sequent, limits)?;
125            let pair = |&(x, y): &(u32, u32)| (VertexId::new(x), VertexId::new(y));
126            let links: Vec<(VertexId, VertexId)> = net.links.iter().map(pair).collect();
127            let cuts: Vec<(VertexId, VertexId)> = net.cuts.iter().map(pair).collect();
128            let criterion = Criterion {
129                mix: net.mix,
130                order: net.order.map_or(Order::Commutative, Order::from),
131            };
132            ProofStructure::with_cuts(forest, criterion, &cuts, &links)
133        };
134        build().map_err(wire::fail)
135    }
136}
137
138/// The serialized form of a proof structure with boxes. Its keys:
139/// - `version`, its level;
140/// - `sequent`;
141/// - `mix`, whether Mix is allowed;
142/// - `vertices`, the vertices after the roots, each `[occurrence, parent,
143///   box]`. `parent` is `null` for an end of a cut link. `box` is the `!`
144///   vertex of the innermost box around the vertex, or `null` outside
145///   every box;
146/// - `cuts`, the cut links, where there are some;
147/// - `links`, the axiom links;
148/// - `weakenings`, each a `?` vertex without copies and the literal it
149///   hangs on.
150///
151/// Links and weakenings are pairs of vertex ids.
152#[derive(Clone, Debug, Serialize, Deserialize)]
153struct Boxed {
154    /// The wire level.
155    #[serde(
156        default,
157        skip_serializing_if = "Option::is_none",
158        deserialize_with = "wire::version"
159    )]
160    version: Option<u32>,
161    /// The sequent.
162    sequent: Sequent,
163    /// Whether Mix is allowed.
164    mix: bool,
165    /// The vertices after the roots.
166    vertices: Vec<(u32, Option<u32>, Option<u32>)>,
167    /// The cut links, written where there are some.
168    #[serde(default, skip_serializing_if = "Vec::is_empty")]
169    cuts: Vec<(u32, u32)>,
170    /// The axiom links.
171    links: Vec<(u32, u32)>,
172    /// The weakenings.
173    weakenings: Vec<(u32, u32)>,
174}
175
176impl Serialize for MellStructure {
177    /// Serializes the structure as a document: its level, sequent,
178    /// whether Mix is allowed, vertices, cut links, links and weakenings.
179    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
180        boxed(self).serialize(serializer)
181    }
182}
183
184/// Returns the form of a proof structure with boxes, with its level.
185fn boxed(net: &MellStructure) -> Boxed {
186    let parts = net.parts();
187    let pair = |&(x, y): &(VertexId, VertexId)| (x.get(), y.get());
188    Boxed {
189        version: Some(wire::BOXES.max(wire::level_of_sequent(net.forest().sequent()))),
190        sequent: Sequent::from(net.forest().sequent()),
191        mix: net.criterion().mix,
192        vertices: parts
193            .vertices
194            .iter()
195            .map(|p| {
196                (
197                    p.occurrence.get(),
198                    p.parent.map(VertexId::get),
199                    p.inside.map(VertexId::get),
200                )
201            })
202            .collect(),
203        cuts: parts.cuts.iter().map(pair).collect(),
204        links: parts.links.iter().map(pair).collect(),
205        weakenings: parts.weakenings.iter().map(pair).collect(),
206    }
207}
208
209/// A step of a cut elimination on a net, as its record writes it.
210#[derive(Serialize)]
211struct StepForm {
212    /// The cut link reduced, from its end in a cut formula's tree.
213    cut: (u32, u32),
214    /// The case.
215    case: crate::linear::proofs::cut::Case,
216    /// The vertex the step acted at besides the cut link.
217    #[serde(skip_serializing_if = "Option::is_none")]
218    above: Option<u32>,
219}
220
221/// A cut elimination on a net, as its record writes it.
222#[derive(Serialize)]
223struct EliminationForm<'a, F> {
224    /// The wire level.
225    version: u32,
226    /// The net reached, nested.
227    net: F,
228    /// The steps.
229    steps: Vec<StepForm>,
230    /// `cut_free`, or `refused` with the reason.
231    end: &'static str,
232    /// Why the elimination was refused, in an error's form.
233    #[serde(skip_serializing_if = "Option::is_none")]
234    reason: Option<&'a crate::Error>,
235}
236
237/// Writes the record of a cut elimination. `net` is the form of the net
238/// it reached, without its level, which is `version`.
239fn record<S: Serializer, F: Serialize>(
240    serializer: S,
241    net: F,
242    version: u32,
243    steps: &[crate::linear::nets::cut::Step],
244    end: &crate::linear::proofs::cut::End,
245) -> Result<S::Ok, S::Error> {
246    use crate::linear::proofs::cut::End;
247    let reason = match end {
248        End::CutFree => None,
249        End::Refused(refusal) => Some(crate::Error::Refused(refusal.clone())),
250    };
251    EliminationForm {
252        version,
253        net,
254        steps: steps
255            .iter()
256            .map(|step| StepForm {
257                cut: (step.cut.0.get(), step.cut.1.get()),
258                case: step.case,
259                above: step.above.map(VertexId::get),
260            })
261            .collect(),
262        end: if reason.is_some() {
263            "refused"
264        } else {
265            "cut_free"
266        },
267        reason: reason.as_ref(),
268    }
269    .serialize(serializer)
270}
271
272impl Serialize for crate::linear::nets::cut::Elimination<ProofStructure> {
273    /// Serializes the elimination as a document: the net reached, at the
274    /// level of its form, the steps and how it ended.
275    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
276        let mut net = form(&self.net);
277        let version = net.version.take().unwrap_or(wire::BASE);
278        record(serializer, net, version, &self.steps, &self.end)
279    }
280}
281
282impl Serialize for crate::linear::nets::cut::Elimination<MellStructure> {
283    /// Serializes the elimination as a document: the net reached, at the
284    /// level of its form, the steps and how it ended.
285    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
286        let mut net = boxed(&self.net);
287        let version = net.version.take().unwrap_or(wire::BOXES);
288        record(serializer, net, version, &self.steps, &self.end)
289    }
290}
291
292impl<'a> Deserialize<'a> for MellStructure {
293    /// Deserializes a structure within the default limits, as
294    /// [`wire::upgrade`] does.
295    fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error> {
296        Self::read(deserializer, &Limits::default())
297    }
298}
299
300impl crate::sealed::Readable for MellStructure {}
301
302impl Readable for MellStructure {
303    const FORM: &'static str = "proof structure with boxes";
304
305    /// Reads a structure. Builds the forest of its sequent within the
306    /// limits, and validates its vertices, links and weakenings as
307    /// [`MellStructure::from_parts`] does, its graph within
308    /// `limits.memory_bytes`. Whether it is a proof net is for
309    /// [`MellStructure::is_correct`] to say.
310    fn read<'de, D: Deserializer<'de>>(deserializer: D, limits: &Limits) -> Result<Self, D::Error> {
311        let boxed = Boxed::deserialize(deserializer)?;
312        let build = || {
313            let sequent = crate::linear::Sequent::try_from(boxed.sequent)?;
314            let forest = Forest::from_owned(sequent, limits)?;
315            let pair = |&(x, y): &(u32, u32)| (VertexId::new(x), VertexId::new(y));
316            let parts = Parts {
317                vertices: boxed
318                    .vertices
319                    .iter()
320                    .map(|&(o, p, b)| match p {
321                        Some(p) => {
322                            Placed::new(OccId::new(o), VertexId::new(p), b.map(VertexId::new))
323                        }
324                        None => Placed::cut(OccId::new(o), b.map(VertexId::new)),
325                    })
326                    .collect(),
327                cuts: boxed.cuts.iter().map(pair).collect(),
328                links: boxed.links.iter().map(pair).collect(),
329                weakenings: boxed.weakenings.iter().map(pair).collect(),
330            };
331            let criterion = Criterion {
332                mix: boxed.mix,
333                order: Order::Commutative,
334            };
335            MellStructure::from_parts(forest, criterion, &parts, limits)
336        };
337        build().map_err(wire::fail)
338    }
339}