panproto_inst/complement.rs
1//! The complement: data discarded when projecting an instance forward.
2//!
3//! A [`Complement`] records everything a forward projection (a lens `get` or a
4//! `restrict_with_complement`) drops from a source [`WInstance`](crate::WInstance),
5//! so that the backward direction can reconstruct the original source from a
6//! (possibly modified) view. It is the shared complement type for both the
7//! asymmetric lens in `panproto-lens` and the polynomial-functor restrict
8//! pipeline in [`crate::poly`].
9//!
10//! Not every field is populated by every producer: the lens `get` path fills
11//! the structural-reconstruction fields (dropped nodes/arcs/fans, contraction
12//! choices, parent map, arc-edge disambiguators, snapshots, synthesized
13//! nodes, source fingerprint); the restrict pipeline additionally records
14//! [`Complement::contracted_into`], the surviving ancestor each dropped node
15//! collapsed into. Unused fields stay empty and are omitted from the
16//! serialized form.
17
18use std::collections::{HashMap, HashSet};
19
20use panproto_schema::Edge;
21
22use crate::fan::Fan;
23use crate::metadata::Node;
24use crate::value::{FieldPresence, Value};
25
26/// The complement: data discarded by a forward projection, needed by the
27/// backward direction to restore the original source instance.
28///
29/// When a forward projection maps a source instance to a target view, some
30/// nodes, arcs, and structural decisions are lost. The complement records all
31/// of this so the backward direction can reconstruct the full source.
32#[derive(Clone, Debug, Default, serde::Serialize, serde::Deserialize)]
33pub struct Complement {
34 /// Nodes from the source that do not appear in the target view.
35 pub dropped_nodes: HashMap<u32, Node>,
36 /// Arcs from the source that do not appear in the target view.
37 pub dropped_arcs: Vec<(u32, u32, Edge)>,
38 /// Fans from the source whose parent or children were dropped.
39 pub dropped_fans: Vec<Fan>,
40 /// Resolver decisions made during ancestor contraction.
41 pub contraction_choices: HashMap<(u32, u32), Edge>,
42 /// Original parent mapping before contraction.
43 pub original_parent: HashMap<u32, u32>,
44 /// Fingerprint of the source schema at projection time, used by the
45 /// backward direction to validate that the complement matches the lens's
46 /// source schema.
47 #[serde(default)]
48 pub source_fingerprint: u64,
49 /// Pre-transform `extra_fields` for nodes that had `field_transforms`
50 /// applied. Used by the backward direction to restore original field
51 /// values.
52 #[serde(default, skip_serializing_if = "HashMap::is_empty")]
53 pub original_extra_fields: HashMap<u32, HashMap<String, Value>>,
54 /// Exact edge used for every arc in the view, keyed by
55 /// `(parent_id, child_id)`. This makes the backward direction
56 /// deterministic when the source schema has parallel edges between the
57 /// same vertex pair, ensuring the cartesian lift is unique.
58 #[serde(default, skip_serializing_if = "HashMap::is_empty")]
59 pub arc_edges: HashMap<(u32, u32), Edge>,
60 /// The source instance's arcs in order, as `(parent_id, child_id)`.
61 ///
62 /// Arc order is not incidental: the children of a collection node are
63 /// its elements *in sequence*, so serialization reads array order
64 /// straight off it. The backward direction rebuilds arcs by walking
65 /// `original_parent`, a `HashMap`, whose iteration order varies between
66 /// runs, which reorders every array it reconstructs. Recording the
67 /// sequence here is what lets `put` put them back as they were.
68 ///
69 /// Empty on a complement produced before this was recorded, in which
70 /// case the backward direction falls back to a deterministic order
71 /// rather than a random one.
72 #[serde(default, skip_serializing_if = "Vec::is_empty")]
73 pub arc_order: Vec<(u32, u32)>,
74 /// Pre-coercion `node.value` for nodes that had `__value__` field
75 /// transforms applied. Used by the backward direction to restore the
76 /// original leaf value.
77 #[serde(default, skip_serializing_if = "HashMap::is_empty")]
78 pub original_values: HashMap<u32, Option<FieldPresence>>,
79 /// View node ids synthesized during forward evaluation by the nest-style
80 /// `expansion_path` mechanism. These nodes exist in the view (to satisfy
81 /// the target schema's multi-hop path) but have no counterpart in the
82 /// source instance. The backward direction drops them when reconstructing
83 /// the source.
84 #[serde(default, skip_serializing_if = "HashSet::is_empty")]
85 pub synthesized_nodes: HashSet<u32>,
86 /// For each dropped node, the surviving node it contracted into (its
87 /// nearest surviving ancestor). Populated by the restrict pipeline's
88 /// ancestor contraction; the fiber of a target node is its direct
89 /// preimage together with every source node recorded here as contracted
90 /// into it.
91 #[serde(default, skip_serializing_if = "HashMap::is_empty")]
92 pub contracted_into: HashMap<u32, u32>,
93}
94
95impl Complement {
96 /// Create an empty complement (no data discarded).
97 #[must_use]
98 pub fn empty() -> Self {
99 Self::default()
100 }
101
102 /// Returns `true` if every field of the complement is unset.
103 ///
104 /// The [`source_fingerprint`](Self::source_fingerprint) is provenance
105 /// metadata rather than discarded data, so a projection that records
106 /// only a fingerprint counts as empty.
107 ///
108 /// This is a statement about the *representation*, not about
109 /// information loss: a lens that discards nothing still populates
110 /// `original_parent`, `arc_order`, and `arc_edges`, so it is not empty
111 /// by this measure. For the question "did this projection lose
112 /// anything", see [`residue_is_trivial`](Self::residue_is_trivial).
113 #[must_use]
114 pub fn is_empty(&self) -> bool {
115 self.dropped_nodes.is_empty()
116 && self.dropped_arcs.is_empty()
117 && self.dropped_fans.is_empty()
118 && self.contraction_choices.is_empty()
119 && self.original_parent.is_empty()
120 && self.original_extra_fields.is_empty()
121 && self.arc_edges.is_empty()
122 && self.arc_order.is_empty()
123 && self.original_values.is_empty()
124 && self.synthesized_nodes.is_empty()
125 && self.contracted_into.is_empty()
126 }
127
128 /// Returns `true` when this complement carries no information that the
129 /// view lacks, i.e. when the complement is terminal.
130 ///
131 /// A lens with complement is a decomposition `S ≅ V × C`: `get` splits
132 /// a source into a view and a complement, and `put` reassembles it. The
133 /// complement's fields divide into two kinds under that reading, and
134 /// only one of them is `C`:
135 ///
136 /// * **Residue.** Dropped nodes, arcs, and fans; snapshots of values
137 /// the forward pass overwrote; contraction choices. This is the
138 /// information present in `S` and absent from `V`, so it *is* the
139 /// complement, and no amount of looking at `V` recovers it.
140 /// * **Bookkeeping.** `original_parent`, `arc_order`, `arc_edges`.
141 /// These record the shape of the reassembly, which is a function of
142 /// the view's own structure together with the source schema rather
143 /// than of the particular record. They make `put` cheap and
144 /// deterministic; they carry no information the view lacks.
145 ///
146 /// So `C ≅ 1` exactly when the residue is empty, whatever bookkeeping
147 /// is present. That is the condition under which `S ≅ V × 1 ≅ V`, and
148 /// therefore the condition under which a source can be reconstructed
149 /// from a view alone. See `panproto_lens::put_without_complement`.
150 #[must_use]
151 pub fn residue_is_trivial(&self) -> bool {
152 self.dropped_nodes.is_empty()
153 && self.dropped_arcs.is_empty()
154 && self.dropped_fans.is_empty()
155 && self.contraction_choices.is_empty()
156 && self.original_extra_fields.is_empty()
157 && self.original_values.is_empty()
158 && self.contracted_into.is_empty()
159 }
160}