Skip to main content

kernel/graph/
cross_graph.rs

1// Copyright 2026 Mark AB (markik)
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Cross-graph node copy — the kernel half of the tear-out "fork" / cross-graph
5//! composability gesture (tear-out brief §7.5; tearout-composability plan C4).
6//!
7//! A node→node derivation *within* one graph rides a petgraph `Provenance`
8//! edge. A cross-graph copy's source node lives in a *different* graph, so the
9//! relation cannot be a petgraph edge; the derivation is recorded on the minted
10//! node as a [`NodeDerivation`] instead (see `node.rs` / `types.rs`). That
11//! record is the lineage pointer back to the source and projects to a
12//! `<copy> {provenance predicate} <source>` statement under the RDF projection.
13//!
14//! WASM-clean: must compile to `wasm32-unknown-unknown` (mirrors `graph/mod.rs`).
15
16use euclid::default::Point2D;
17use uuid::Uuid;
18
19use super::node_facets::{PROVENANCE_DERIVATIONS, VisitHistoryFacet};
20use super::{Graph, Node, NodeKey, ProvenanceSubKind};
21use crate::types::NodeDerivation;
22
23impl Graph {
24    /// Copy `source`'s content into this graph, minting a fresh node and
25    /// recording cross-graph derivation provenance back to the source.
26    ///
27    /// `source` is a donor [`Node`] from another [`Graph`]; `source_graph` is the
28    /// donor graph's id (the constellation `GraphId` rendered as a string), or
29    /// `None` when unknown / same-graph. The copy is a *new entity*: it gets a
30    /// fresh identity, and its **content** (title, tags, classifications, open
31    /// properties, address, visuals, viewer preferences) is cloned, while its
32    /// **identity / runtime / session / arrangement** state is reset (fresh id,
33    /// unpinned, no frame hints; browser-runtime state lives in the host's
34    /// `BrowserNodeState` sidecar and never travels with a copy). A
35    /// [`NodeDerivation`] records `(CopiedFrom, source.id, source_graph)` so the
36    /// lineage survives and projects to a `wasDerivedFrom` statement.
37    ///
38    /// The donor's `import_provenance` is intentionally *not* carried over: that
39    /// describes how the donor entered *its* graph from an external source; the
40    /// copy's provenance is the derivation record, not the donor's import.
41    ///
42    /// Not available on `wasm32` (mints a random id, like [`add_node`]); use
43    /// [`copy_node_from_with_id`](Self::copy_node_from_with_id) with a
44    /// host-provided UUID there.
45    ///
46    /// [`add_node`]: Self::add_node
47    #[cfg(not(target_arch = "wasm32"))]
48    pub fn copy_node_from(
49        &mut self,
50        source: &Node,
51        source_graph: Option<String>,
52        position: Point2D<f32>,
53    ) -> NodeKey {
54        self.copy_node_from_with_id(Uuid::new_v4(), source, source_graph, position)
55    }
56
57    /// [`copy_node_from`](Self::copy_node_from) with a caller-supplied id (the
58    /// wasm-clean entry point, mirroring
59    /// [`add_node_with_id`](Self::add_node_with_id)).
60    pub fn copy_node_from_with_id(
61        &mut self,
62        id: Uuid,
63        source: &Node,
64        source_graph: Option<String>,
65        _position: Point2D<f32>,
66    ) -> NodeKey {
67        let derivation = NodeDerivation {
68            sub_kind: ProvenanceSubKind::CopiedFrom,
69            source_node: source.id.to_string(),
70            source_graph,
71        };
72        let url = source.primary_address().as_url_str().to_string();
73        let mut container = source.container.clone();
74        container.id = id;
75        // Deliberately NOT carried: a copy is un-resided. Carrying the LogId
76        // would leave two nodes bearing one world file.
77        container.nested = None;
78
79        let key = self.inner.insert(Node {
80            // --- container content: cloned from the source ---
81            container,
82            // References copy freely: the blob is content-addressed and shared,
83            // so a cross-graph copy costs ~40 bytes per role, not a duplicated
84            // image.
85            images: source.images.clone(),
86        });
87        self.set_node_facet(key, PROVENANCE_DERIVATIONS, &vec![derivation]);
88        self.set_node_facet(
89            key,
90            super::node_facets::VISIT_HISTORY,
91            &VisitHistoryFacet {
92                last_visited_ms: Some(Self::epoch_ms()),
93                last_session_visited: 0,
94            },
95        );
96
97        self.url_to_nodes.entry(url).or_default().push(key);
98        self.bump_revision();
99        key
100    }
101
102    /// [`copy_node_from`](Self::copy_node_from) taking plain `x` / `y` screen-graph
103    /// coords, so a host can place the copy without depending on `euclid`. (Tear-out
104    /// gestures G5.)
105    #[cfg(not(target_arch = "wasm32"))]
106    pub fn copy_node_from_xy(
107        &mut self,
108        source: &Node,
109        source_graph: Option<String>,
110        x: f32,
111        y: f32,
112    ) -> NodeKey {
113        self.copy_node_from(source, source_graph, Point2D::new(x, y))
114    }
115
116    /// Copy the connected component containing `seed` (a node in `source`) into this
117    /// graph: the kernel half of a tear-out **fork** (the reachable-subgraph snapshot,
118    /// tear-out brief §4.3). Each node is minted fresh (with a `CopiedFrom`
119    /// [`NodeDerivation`] back to its source); the component's internal edges are
120    /// re-pointed onto the new nodes by cloning each edge's payload verbatim. Edges
121    /// leaving the component are dropped (the snapshot is closed under the component).
122    /// Returns the [`ComponentCopy`]: the new keys plus the `source id → new id`
123    /// remap the host's facet-carry maps donor facets through (G4-R R0 — positions
124    /// and every other per-node character ride `arrangement.*` / `web.*` / … facets,
125    /// not the graph, so the fork's layout carry needs this mapping).
126    /// (Tear-out gestures G4.)
127    #[cfg(not(target_arch = "wasm32"))]
128    pub fn copy_component_from(
129        &mut self,
130        source: &Graph,
131        seed: Uuid,
132        source_graph: Option<String>,
133    ) -> ComponentCopy {
134        use petgraph::visit::{EdgeRef, IntoEdgeReferences};
135        let Some(seed_key) = source.get_node_key_by_id(seed) else {
136            return ComponentCopy::default();
137        };
138        // The weakly-connected component containing the seed (every node is in exactly
139        // one; fall back to the lone seed if the partition somehow omits it).
140        let component = source
141            .weakly_connected_components()
142            .into_iter()
143            .find(|c| c.contains(&seed_key))
144            .unwrap_or_else(|| vec![seed_key]);
145        // Copy each node, mapping its old key to the fresh one for edge re-pointing
146        // (and its old id to the fresh id for the host's facet-carry).
147        let mut key_remap: std::collections::HashMap<NodeKey, NodeKey> =
148            std::collections::HashMap::with_capacity(component.len());
149        let mut copy = ComponentCopy {
150            new_keys: Vec::with_capacity(component.len()),
151            id_remap: Vec::with_capacity(component.len()),
152        };
153        for old_key in component {
154            if let Some(node) = source.inner.node(old_key) {
155                let source_id = node.id;
156                // Position is no longer a node field; the copy is placed by the
157                // destination's layout (seiche / arrangement facets), not carried over.
158                let new_key = self.copy_node_from(node, source_graph.clone(), Point2D::zero());
159                // Content facets travel with a component copy. Runtime,
160                // arrangement, visit, and import provenance do not; the host
161                // may separately carry view/foreign facets through `id_remap`.
162                for facet in [
163                    super::node_facets::PRESENTATION_TAGS,
164                    super::node_facets::SEMANTIC_CLASSIFICATIONS,
165                    super::node_facets::SEMANTIC_PROPERTIES,
166                ] {
167                    let facet_id = chartulary::FacetId::new(facet);
168                    if let Some(value) = source.facets.get(&source_id, &facet_id) {
169                        self.facets
170                            .set(
171                                self.inner.node(new_key).expect("inserted copy").id,
172                                facet_id,
173                                value.clone(),
174                                &chartulary::AcceptAll,
175                            )
176                            .expect("AcceptAll cannot reject copied content");
177                    }
178                }
179                key_remap.insert(old_key, new_key);
180                copy.new_keys.push(new_key);
181                if let Some(new_node) = self.inner.node(new_key) {
182                    copy.id_remap.push((source_id, new_node.id));
183                }
184            }
185        }
186        // Re-point the component's internal edges (both endpoints copied): clone each
187        // edge's payload verbatim onto the new node pair.
188        for edge in source.inner.inner().edge_references() {
189            if let (Some(&from), Some(&to)) =
190                (key_remap.get(&edge.source()), key_remap.get(&edge.target()))
191            {
192                self.inner.connect(from, to, edge.weight().clone());
193            }
194        }
195        self.bump_revision();
196        copy
197    }
198}
199
200/// The result of [`Graph::copy_component_from`]: the minted keys plus the
201/// `(source id, new id)` pairs, in copy order. The id remap is the seam the
202/// host's facet-carry maps donor facets through (a forked node keeps its whole
203/// per-node character — `arrangement.*`, `web.*`, foreign namespaces — by
204/// copying facets from `source` to `new`).
205#[derive(Clone, Debug, Default)]
206pub struct ComponentCopy {
207    /// The fresh node keys in this graph, in copy order.
208    pub new_keys: Vec<NodeKey>,
209    /// `(source node id, minted node id)` per copied node, in copy order.
210    pub id_remap: Vec<(Uuid, Uuid)>,
211}
212
213#[cfg(all(test, not(target_arch = "wasm32")))]
214mod tests {
215    use super::*;
216    use std::collections::HashSet;
217
218    fn donor_with_content() -> (Graph, NodeKey) {
219        let mut a = Graph::new();
220        let key = a.add_node(
221            "https://example.com/article".to_string(),
222            Point2D::new(1.0, 2.0),
223        );
224        {
225            let node = a.inner.node_mut(key).unwrap();
226            node.title = "An Article".to_string();
227            node.tags = HashSet::from(["read-later".to_string(), "research".to_string()]);
228        }
229        a.append_node_property(
230            key,
231            crate::types::NodeProperty::new(
232                "https://schema.org/datePublished".to_string(),
233                "2026-01-01".to_string(),
234            ),
235        );
236        a.set_node_pinned(key, true);
237        (a, key)
238    }
239
240    #[test]
241    fn copy_mints_a_fresh_node_cloning_content_with_derivation() {
242        let (a, src_key) = donor_with_content();
243        let source = a.get_node(src_key).unwrap().clone();
244        let source_id = source.id;
245
246        let mut b = Graph::new();
247        let rev_before = b.revision();
248        let copy_key =
249            b.copy_node_from(&source, Some("graph-A".to_string()), Point2D::new(9.0, 9.0));
250        assert!(
251            b.revision() > rev_before,
252            "copying a node in is structural and advances the revision"
253        );
254        let copy = b.get_node(copy_key).unwrap();
255
256        // Fresh identity, content cloned.
257        assert_ne!(copy.id, source_id, "copy is a new entity");
258        assert_eq!(copy.title, "An Article");
259        assert_eq!(copy.tags, source.tags);
260        assert_eq!(copy.url(), source.url(), "same content, same address");
261
262        // Position is not a node field (not inherited, not carried); the copy is
263        // placed by the destination's layout.
264        assert_eq!(
265            b.node_is_pinned(copy_key),
266            Some(false),
267            "pin is per-placement"
268        );
269
270        // Derivation records the lineage back to the source.
271        let derivations = b.node_derivations(copy_key).unwrap();
272        assert_eq!(derivations.len(), 1);
273        let d = &derivations[0];
274        assert_eq!(d.sub_kind, ProvenanceSubKind::CopiedFrom);
275        assert_eq!(d.source_node, source_id.to_string());
276        assert_eq!(d.source_graph.as_deref(), Some("graph-A"));
277
278        // The copy is discoverable by its address in the destination index.
279        assert_eq!(b.get_nodes_by_url(source.url()).len(), 1);
280    }
281
282    #[test]
283    fn copy_does_not_carry_the_donor_import_provenance() {
284        let (mut a, src_key) = donor_with_content();
285        a.set_node_import_provenance(
286            src_key,
287            vec![crate::types::NodeImportProvenance {
288                source_id: "firefox".to_string(),
289                source_label: "Firefox bookmarks".to_string(),
290            }],
291        );
292        let source = a.get_node(src_key).unwrap().clone();
293
294        let mut b = Graph::new();
295        let copy_key = b.copy_node_from(&source, None, Point2D::zero());
296        let copy = b.get_node(copy_key).unwrap();
297
298        assert!(
299            b.node_import_provenance(copy_key).unwrap().is_empty(),
300            "donor import provenance is the donor's, not the copy's"
301        );
302        assert_eq!(
303            b.node_derivations(copy_key).unwrap()[0].source_graph,
304            None,
305            "same-graph / unknown source graph"
306        );
307    }
308
309    #[test]
310    fn copy_component_clones_the_connected_subgraph_with_edges_and_provenance() {
311        use crate::graph::{EdgeAssertion, SemanticSubKind};
312        let mut a = Graph::new();
313        let k1 = a.add_node("https://a.com/1".to_string(), Point2D::new(0.0, 0.0));
314        let k2 = a.add_node("https://a.com/2".to_string(), Point2D::new(1.0, 0.0));
315        let _k3 = a.add_node("https://a.com/3".to_string(), Point2D::new(9.0, 9.0)); // disconnected
316        a.assert_relation(
317            k1,
318            k2,
319            EdgeAssertion::Semantic {
320                sub_kind: SemanticSubKind::Hyperlink,
321                label: None,
322                decay_progress: None,
323            },
324        );
325        let seed = a.get_node(k1).unwrap().id;
326
327        let mut b = Graph::new();
328        let copy = b.copy_component_from(&a, seed, Some("graph-A".to_string()));
329
330        // The connected component is {k1, k2}; the disconnected k3 is not pulled in.
331        assert_eq!(
332            copy.new_keys.len(),
333            2,
334            "copied the 2-node component, not the lone disconnected node"
335        );
336        assert_eq!(b.nodes().count(), 2);
337        // The component's internal edge is re-pointed onto the copies.
338        assert_eq!(b.relations().count(), 1, "the internal edge is re-pointed");
339        // Each copy records `CopiedFrom` provenance back to the source graph.
340        for (key, _) in b.nodes() {
341            let derivations = b.node_derivations(key).unwrap();
342            assert_eq!(derivations.len(), 1);
343            assert_eq!(derivations[0].sub_kind, ProvenanceSubKind::CopiedFrom);
344            assert_eq!(derivations[0].source_graph.as_deref(), Some("graph-A"));
345        }
346        // The id remap pairs each source id with its minted copy's id — the seam
347        // the host's facet-carry maps donor facets through (G4-R R0).
348        assert_eq!(copy.id_remap.len(), 2);
349        for (source_id, new_id) in &copy.id_remap {
350            assert_ne!(source_id, new_id, "a copy is a new entity");
351            let (_, source_node) = a.get_node_by_id(*source_id).map(|(k, n)| (k, n)).unwrap();
352            let (_, new_node) = b.get_node_by_id(*new_id).map(|(k, n)| (k, n)).unwrap();
353            assert_eq!(source_node.url(), new_node.url(), "pairs align by content");
354            assert_eq!(
355                b.node_derivations(b.get_node_key_by_id(*new_id).unwrap())
356                    .unwrap()[0]
357                    .source_node,
358                source_id.to_string()
359            );
360        }
361    }
362}