Skip to main content

kernel/graph/
merge.rs

1// Copyright 2026 Mark Alan Boykin
2// This Source Code Form is subject to the terms of the Mozilla Public
3// License, v. 2.0. If a copy of the MPL was not distributed with this
4// file, You can obtain one at https://mozilla.org/MPL/2.0/.
5// SPDX-License-Identifier: MPL-2.0
6
7//! Importing one graph into another as edits: what a codicil import writes
8//! into a session's journal.
9//!
10//! Reservoir plan V2, ยง7 item 27. An import used to rebuild the graph from the
11//! union of two snapshots and swap it in, which a journal cannot record. The
12//! same union is written here as ordinary edits:
13//! - a node the live graph lacks arrives whole, through the edits undo uses to
14//!   bring back a removed node, and with its images;
15//! - a node both graphs hold keeps its own fields, and the incoming facets
16//!   overwrite its own;
17//! - the incoming relations join the live ones between the same two nodes, as
18//!   a snapshot load restores a union.
19//!
20//! The rebuild also gave every node the default-valued facets its empty legacy
21//! columns import as. These edits give none: the incoming graph carries its
22//! codicil's facet store whole, as a session loads its own. No codicil carries
23//! column data, since canonical saves have written the columns empty since
24//! before the first codicil schema.
25
26use std::collections::BTreeSet;
27
28use euclid::default::Point2D;
29use uuid::Uuid;
30
31use super::Graph;
32use super::capture::CapturedDelta;
33use super::revert::{Revert, edges_between, node_state};
34use crate::persistence::PersistedEdge;
35
36/// The edits that import `incoming` into `live`. `incoming` is a codicil's
37/// graph with the codicil's facet store laid in whole, not over what its
38/// snapshot's legacy columns import.
39/// This compatibility path stops on resources until resource-aware import lands.
40pub fn import_edits(live: &Graph, incoming: &Graph) -> Vec<CapturedDelta> {
41    assert!(
42        incoming.resources.node_count() == 0
43            && incoming.resources.edge_count() == 0
44            && incoming.shown_resources.is_empty(),
45        "surface-only import cannot preserve resource records"
46    );
47    let mut edits = Vec::new();
48    for (_, node) in incoming.nodes() {
49        let (id, node_id) = (node.id, node.id.to_string());
50        if live.get_node_by_id(id).is_none() {
51            let mut made = Revert::default();
52            made.recreate(
53                id,
54                &node_state(incoming, id).expect("an incoming node has a state"),
55            );
56            edits.extend(made.edits);
57            edits.extend(node.images.iter().map(|(role, image)| {
58                CapturedDelta::ReplaySetNodeImageById {
59                    node_id: node_id.clone(),
60                    role: *role,
61                    image: *image,
62                }
63            }));
64            continue;
65        }
66        let Some(facets) = incoming.facets().facets_of(&id) else {
67            continue;
68        };
69        for (facet, value) in facets.iter() {
70            if live.facets().get(&id, facet) != Some(value) {
71                edits.push(CapturedDelta::ReplaySetNodeFacetById {
72                    node_id: node_id.clone(),
73                    facet: facet.as_str().to_string(),
74                    value_json: value.to_string(),
75                });
76            }
77        }
78    }
79
80    let id_of = |key| incoming.get_node(key).map(|node| node.id);
81    let pairs: BTreeSet<(Uuid, Uuid)> = incoming
82        .relations()
83        .filter_map(|relation| Some((id_of(relation.from)?, id_of(relation.to)?)))
84        .collect();
85    for (from, to) in pairs {
86        let held = edges_between(live, from, to);
87        let joined = joined(from, to, &held, &edges_between(incoming, from, to));
88        if joined != held {
89            edits.push(CapturedDelta::ReplaySetEdgesByIds {
90                from_id: from.to_string(),
91                to_id: to.to_string(),
92                edges: joined,
93            });
94        }
95    }
96    edits
97}
98
99/// The relations from `from` to `to` once `incoming`'s are restored after
100/// `held`, worked out on a scratch pair of nodes.
101fn joined(
102    from: Uuid,
103    to: Uuid,
104    held: &[PersistedEdge],
105    incoming: &[PersistedEdge],
106) -> Vec<PersistedEdge> {
107    let mut scratch = Graph::new();
108    let origin = Point2D::new(0.0, 0.0);
109    let from_key = scratch.add_node_with_id(from, format!("urn:uuid:{from}"), origin);
110    let to_key = if to == from {
111        from_key
112    } else {
113        scratch.add_node_with_id(to, format!("urn:uuid:{to}"), origin)
114    };
115    for edge in held.iter().chain(incoming) {
116        scratch.restore_persisted_edge(from_key, to_key, edge);
117    }
118    scratch.persisted_edges_between(from_key, to_key)
119}
120
121#[cfg(test)]
122mod tests {
123    use std::collections::{BTreeMap, HashSet};
124
125    use serde_json::Value;
126
127    use chartulary::AcceptAll;
128
129    use super::*;
130    use crate::graph::revert::NodeState;
131    use crate::graph::revert::tests::{add, apply_all, facet, id, relate, tag, title};
132    use crate::graph::{EdgeAssertion, NavigationTrigger, NodeFacetStore, SemanticSubKind};
133    use crate::persistence::GraphSnapshot;
134    use crate::types::{ImageRef, ImageRole};
135
136    #[test]
137    fn surface_import_stops_before_losing_resources_with_legacy_positive_control() {
138        let live = Graph::new();
139        let mut legacy = Graph::new();
140        legacy.add_node_with_id(
141            id(1),
142            "https://surface.test/".into(),
143            Point2D::new(0.0, 0.0),
144        );
145        let edits = import_edits(&live, &legacy);
146        assert!(!edits.is_empty());
147        let mut accepted = live.clone();
148        apply_all(&mut accepted, &edits);
149        assert_eq!(accepted.node_count(), 1);
150        assert!(accepted.get_node_by_id(id(1)).is_some());
151        let mut snapshot = legacy.to_snapshot();
152        let iri = "https://resource.test/page";
153        snapshot
154            .resources
155            .push(crate::persistence::PersistedResourceRecord {
156                canonical_iri: iri.into(),
157                facets: vec![],
158            });
159        let incoming = Graph::try_from_snapshot(&snapshot).unwrap();
160        assert!(
161            std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
162                import_edits(&live, &incoming)
163            }))
164            .is_err()
165        );
166        assert_eq!(live.node_count(), 0);
167        assert!(live.resource_nodes().next().is_none());
168        assert_eq!(incoming.node_count(), 1);
169        assert!(incoming.resource(chartulary::resource_id(iri)).is_some());
170    }
171
172    type Codicil = (GraphSnapshot, NodeFacetStore);
173
174    fn touch(n: u128, at: u64) -> CapturedDelta {
175        CapturedDelta::ReplayTouchNodeLastVisitedById {
176            node_id: id(n).to_string(),
177            timestamp_ms: at,
178        }
179    }
180
181    fn supports(from: u128, to: u128) -> CapturedDelta {
182        CapturedDelta::ReplayAssertRelationByIds {
183            from_id: id(from).to_string(),
184            to_id: id(to).to_string(),
185            assertion: EdgeAssertion::Semantic {
186                sub_kind: SemanticSubKind::Supports,
187                label: None,
188            },
189        }
190    }
191
192    fn traverse(from: u128, to: u128, at: u64) -> CapturedDelta {
193        CapturedDelta::ReplayAppendTraversalByIds {
194            from_id: id(from).to_string(),
195            to_id: id(to).to_string(),
196            trigger: NavigationTrigger::LinkClick,
197            timestamp_ms: at,
198        }
199    }
200
201    fn at_url(n: u128, url: &str) -> CapturedDelta {
202        CapturedDelta::ReplayAddNodeWithIdIfMissing {
203            id: id(n).to_string(),
204            url: url.to_string(),
205            position: [0.0, 0.0],
206        }
207    }
208
209    /// `members` cut from `source` as Graphshell's export cuts a codicil.
210    fn codicil(source: &Graph, members: &[u128]) -> Codicil {
211        let members: HashSet<Uuid> = members.iter().map(|n| id(*n)).collect();
212        let ids: HashSet<String> = members.iter().map(Uuid::to_string).collect();
213        let mut snapshot = source.to_snapshot();
214        snapshot.nodes.retain(|node| ids.contains(&node.node_id));
215        snapshot
216            .edges
217            .retain(|edge| ids.contains(&edge.from_node_id) && ids.contains(&edge.to_node_id));
218        snapshot.import_records.clear();
219        snapshot.fields.clear();
220        snapshot.couplings.clear();
221        snapshot.navigation = Default::default();
222        let mut facets = NodeFacetStore::new();
223        for (node, node_facets) in source.facets().iter() {
224            if !members.contains(node) {
225                continue;
226            }
227            for (facet, value) in node_facets.iter() {
228                facets
229                    .set(*node, facet.clone(), value.clone(), &AcceptAll)
230                    .expect("AcceptAll admits every value");
231            }
232        }
233        (snapshot, facets)
234    }
235
236    /// The import as Graphshell ran it before sessions: the union of the two
237    /// snapshots, rebuilt, with the live facets and then the codicil's laid over.
238    fn rebuilt(live: &Graph, (snapshot, facets): &Codicil) -> Graph {
239        let current = live.facets().clone();
240        let mut merged = live.to_snapshot();
241        let mut known: HashSet<String> = merged
242            .nodes
243            .iter()
244            .map(|node| node.node_id.clone())
245            .collect();
246        for node in &snapshot.nodes {
247            if known.insert(node.node_id.clone()) {
248                merged.nodes.push(node.clone());
249            }
250        }
251        merged.edges.extend(snapshot.edges.iter().cloned());
252        merged.timestamp_secs = snapshot.timestamp_secs;
253        let mut graph = Graph::from_snapshot(&merged);
254        graph.overlay_facets(current).expect("live facets install");
255        graph
256            .overlay_facets(facets.clone())
257            .expect("codicil facets install");
258        graph
259    }
260
261    /// The same import as edits.
262    fn edited(live: &Graph, (snapshot, facets): &Codicil) -> (Graph, Vec<CapturedDelta>) {
263        let mut incoming = Graph::from_snapshot(snapshot);
264        *incoming.facets_mut() = facets.clone();
265        let edits = import_edits(live, &incoming);
266        let mut graph = live.clone();
267        apply_all(&mut graph, &edits);
268        (graph, edits)
269    }
270
271    type Nodes = BTreeMap<Uuid, (NodeState, Vec<(ImageRole, ImageRef)>)>;
272    type Relations = BTreeMap<(Uuid, Uuid), Vec<PersistedEdge>>;
273
274    /// Bucket partition is a compatibility storage detail: an imported claim
275    /// may coalesce with a live pair bucket while a rebuilt legacy snapshot
276    /// still has parallel buckets. Compare the exact assertion multiset per
277    /// directed pair, along with the exposed family set and traversal rows.
278    fn relation_contents(
279        relations: &Relations,
280    ) -> BTreeMap<
281        (Uuid, Uuid),
282        (
283            Vec<crate::persistence::PersistedSemanticStatement>,
284            Vec<String>,
285            Vec<String>,
286        ),
287    > {
288        relations
289            .iter()
290            .map(|(pair, edges)| {
291                let mut assertions: Vec<_> = edges
292                    .iter()
293                    .flat_map(|edge| edge.retained_assertions())
294                    .cloned()
295                    .collect();
296                assertions.sort_by(|left, right| left.statement_id.cmp(&right.statement_id));
297                let families: BTreeSet<_> = edges
298                    .iter()
299                    .flat_map(|edge| &edge.families)
300                    .map(|family| format!("{family:?}"))
301                    .collect();
302                let mut traversals: Vec<_> = edges
303                    .iter()
304                    .filter_map(|edge| edge.traversal.as_ref())
305                    .map(|traversal| serde_json::to_string(traversal).unwrap())
306                    .collect();
307                traversals.sort();
308                (
309                    *pair,
310                    (assertions, families.into_iter().collect(), traversals),
311                )
312            })
313            .collect()
314    }
315
316    /// Every node's state and images, every relation by pair, and the
317    /// relations as the graph reports them, derived ones included.
318    fn whole(graph: &Graph) -> (Nodes, Relations, BTreeSet<String>) {
319        let nodes: Nodes = graph
320            .nodes()
321            .map(|(_, node)| {
322                let images = node.images.iter().map(|(role, image)| (*role, *image));
323                let state = node_state(graph, node.id).expect("a listed node has a state");
324                (node.id, (state, images.collect()))
325            })
326            .collect();
327        let mut relations = Relations::new();
328        for from in nodes.keys() {
329            for to in nodes.keys() {
330                let edges = edges_between(graph, *from, *to);
331                if !edges.is_empty() {
332                    relations.insert((*from, *to), edges);
333                }
334            }
335        }
336        let id_of = |key| graph.get_node(key).map(|node| node.id);
337        let listed = graph
338            .relations()
339            .map(|relation| {
340                let ends = (id_of(relation.from), id_of(relation.to));
341                format!("{ends:?} {:?}", relation.kind)
342            })
343            .collect();
344        (nodes, relations, listed)
345    }
346
347    fn facet_keys(facets: &NodeFacetStore, node: &Uuid) -> BTreeSet<String> {
348        facets
349            .facets_of(node)
350            .map(|facets| {
351                facets
352                    .iter()
353                    .map(|(id, _)| id.as_str().to_string())
354                    .collect()
355            })
356            .unwrap_or_default()
357    }
358
359    /// Whether a facet value says nothing: what an empty legacy column imports as.
360    fn empty(value: &Value) -> bool {
361        match value {
362            Value::Null => true,
363            Value::Bool(value) => !value,
364            Value::Array(values) => values.is_empty(),
365            Value::Object(fields) => fields.values().all(empty),
366            _ => false,
367        }
368    }
369
370    #[test]
371    fn an_import_as_edits_matches_the_rebuilt_union() {
372        let mut live = Graph::new();
373        apply_all(
374            &mut live,
375            &[
376                add(1),
377                title(1, "Live one"),
378                facet(1, "custom.a", "1"),
379                add(2),
380                relate(1, 2),
381                touch(1, 1_700_000_000_000),
382                touch(2, 1_700_000_001_000),
383            ],
384        );
385        let image = ImageRef::new([7; 32], 16, 16);
386        let mut source = Graph::new();
387        apply_all(
388            &mut source,
389            &[
390                add(1),
391                title(1, "Source one"),
392                facet(1, "custom.a", "2"),
393                facet(1, "custom.b", "true"),
394                add(2),
395                at_url(3, "https://site.test/a"),
396                title(3, "Three"),
397                tag(3, "kept"),
398                facet(3, "custom.c", r#"{"x":1}"#),
399                at_url(4, "https://site.test/a/b"),
400                supports(1, 2),
401                relate(3, 4),
402                traverse(3, 1, 1_700_000_002_000),
403                touch(1, 1_700_000_003_000),
404                touch(2, 1_700_000_004_000),
405                touch(3, 1_700_000_005_000),
406                touch(4, 1_700_000_006_000),
407            ],
408        );
409        apply_all(
410            &mut source,
411            &[CapturedDelta::ReplaySetNodeImageById {
412                node_id: id(3).to_string(),
413                role: ImageRole::Favicon,
414                image,
415            }],
416        );
417        let codicil = codicil(&source, &[1, 2, 3, 4]);
418
419        let (imported, edits) = edited(&live, &codicil);
420        let (mut want_nodes, want_relations, want_listed) = whole(&rebuilt(&live, &codicil));
421        // The rebuild's one extra: facets neither graph held, all of them empty.
422        let mut artifacts = BTreeSet::new();
423        for (node, (state, _)) in &mut want_nodes {
424            let mut held = facet_keys(live.facets(), node);
425            held.extend(facet_keys(&codicil.1, node));
426            state.facets.retain(|facet, value| {
427                let artifact = !held.contains(facet);
428                if artifact {
429                    assert!(empty(value), "{facet} = {value} is not an empty column");
430                    artifacts.insert(*node);
431                }
432                !artifact
433            });
434        }
435        assert!(
436            artifacts.contains(&id(1)) && artifacts.contains(&id(3)),
437            "the rebuild added empty facets to a live node and an imported one: {artifacts:?}"
438        );
439        let (nodes, relations, listed) = whole(&imported);
440
441        assert_eq!(nodes, want_nodes);
442        assert_eq!(
443            relations.keys().collect::<Vec<_>>(),
444            want_relations.keys().collect::<Vec<_>>()
445        );
446        assert_eq!(
447            relation_contents(&relations),
448            relation_contents(&want_relations)
449        );
450        assert_eq!(listed, want_listed);
451
452        // What the edits did, as a positive control on the comparison.
453        let (one, _) = &nodes[&id(1)];
454        assert_eq!(
455            one.title, "Live one",
456            "a node both hold keeps its own fields"
457        );
458        assert_eq!(one.facets.get("custom.a"), Some(&serde_json::json!(2)));
459        assert_eq!(one.facets.get("custom.b"), Some(&serde_json::json!(true)));
460        assert_eq!(nodes[&id(3)].1, [(ImageRole::Favicon, image)]);
461        assert_eq!(
462            relations[&(id(1), id(2))]
463                .iter()
464                .flat_map(|edge| edge.retained_assertions())
465                .count(),
466            2,
467            "the incoming relation joins the live one"
468        );
469        assert!(
470            edits.iter().all(|edit| edit.replay().into_write().is_ok()),
471            "every edit has a replay form, so a session can journal it"
472        );
473    }
474
475    #[test]
476    fn importing_what_the_graph_already_holds_writes_nothing() {
477        let mut live = Graph::new();
478        apply_all(
479            &mut live,
480            &[add(1), facet(1, "custom.a", "1"), add(2), relate(1, 2)],
481        );
482        let (_, edits) = edited(&live, &codicil(&live, &[1, 2]));
483        assert!(edits.is_empty(), "{edits:?}");
484    }
485}