Skip to main content

kernel/graph/
cross_graph.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//! Cross-graph node copy — the kernel half of the tear-out "fork" / cross-graph
8//! composability gesture (tear-out brief §7.5; tearout-composability plan C4).
9//!
10//! A node→node derivation *within* one graph rides a petgraph `Provenance`
11//! edge. A cross-graph copy's source node lives in a *different* graph, so the
12//! relation cannot be a petgraph edge; the derivation is recorded on the minted
13//! node as a [`NodeDerivation`] instead (see `node.rs` / `types.rs`). That
14//! record is the lineage pointer back to the source and projects to a
15//! `<copy> {provenance predicate} <source>` statement under the RDF projection.
16//!
17//! WASM-clean: must compile to `wasm32-unknown-unknown` (mirrors `graph/mod.rs`).
18
19use euclid::default::Point2D;
20use uuid::Uuid;
21
22use super::node_facets::PROVENANCE_DERIVATIONS;
23use super::{Graph, Node, NodeKey, ProvenanceSubKind};
24use crate::types::NodeDerivation;
25
26impl Graph {
27    /// Copy `source`'s content into this graph, minting a fresh node and
28    /// recording cross-graph derivation provenance back to the source.
29    ///
30    /// `source` is a donor [`Node`] from another [`Graph`]; `source_graph` is the
31    /// donor graph's id (the constellation `GraphId` rendered as a string), or
32    /// `None` when unknown / same-graph. The copy is a *new entity*: it gets a
33    /// fresh identity, and its **content** (title, tags, classifications, open
34    /// properties, address, visuals, viewer preferences) is cloned, while its
35    /// **identity / runtime / session / arrangement** state is reset (fresh id,
36    /// unpinned, no frame hints; browser-runtime state lives in the host's
37    /// `BrowserNodeState` sidecar and never travels with a copy). A
38    /// [`NodeDerivation`] records `(CopiedFrom, source.id, source_graph)` so the
39    /// lineage survives and projects to a `wasDerivedFrom` statement.
40    ///
41    /// The donor's `import_provenance` is intentionally *not* carried over: that
42    /// describes how the donor entered *its* graph from an external source; the
43    /// copy's provenance is the derivation record, not the donor's import.
44    ///
45    /// Not available on `wasm32` (mints a random id, like [`add_node`]); use
46    /// [`copy_node_from_with_id`](Self::copy_node_from_with_id) with a
47    /// host-provided UUID there.
48    ///
49    /// [`add_node`]: Self::add_node
50    #[cfg(not(target_arch = "wasm32"))]
51    pub fn copy_node_from(
52        &mut self,
53        source: &Node,
54        source_graph: Option<String>,
55        position: Point2D<f32>,
56    ) -> NodeKey {
57        self.copy_node_from_with_id(Uuid::new_v4(), source, source_graph, position)
58    }
59
60    /// [`copy_node_from`](Self::copy_node_from) with a caller-supplied id (the
61    /// wasm-clean entry point, mirroring
62    /// [`add_node_with_id`](Self::add_node_with_id)).
63    pub fn copy_node_from_with_id(
64        &mut self,
65        id: Uuid,
66        source: &Node,
67        source_graph: Option<String>,
68        _position: Point2D<f32>,
69    ) -> NodeKey {
70        let derivation = NodeDerivation {
71            sub_kind: ProvenanceSubKind::CopiedFrom,
72            source_node: source.id.to_string(),
73            source_graph,
74        };
75        let url = source.primary_address().as_url_str().to_string();
76        let mut container = source.container.clone();
77        container.id = id;
78        // Deliberately NOT carried: a copy is un-resided. Carrying the LogId
79        // would leave two nodes bearing one world file.
80        container.nested = None;
81
82        let (key, inserted) = self.insert_surface_node(Node {
83            // --- container content: cloned from the source ---
84            container,
85            // References copy freely: the blob is content-addressed and shared,
86            // so a cross-graph copy costs ~40 bytes per role, not a duplicated
87            // image.
88            images: source.images.clone(),
89        });
90        if !inserted {
91            return key;
92        }
93        self.set_node_facet(key, PROVENANCE_DERIVATIONS, &vec![derivation]);
94        self.set_node_last_visited_at_ms(key, Self::epoch_ms());
95
96        self.url_to_nodes.entry(url).or_default().push(key);
97        self.bump_revision();
98        self.bump_content_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). The component is [`component_members`]' (every family,
119    /// both strata, shown bindings at zero hops; ruling 38), so surfaces joined only by
120    /// a resource relation copy together. Each surface is minted fresh (with a
121    /// `CopiedFrom` [`NodeDerivation`] back to its source); surface edges among the
122    /// copies are re-pointed onto the new nodes by cloning each payload verbatim.
123    /// Resources keep their ids (shared content, as selection Copy retains them): the
124    /// walked resources and the predicate-declaration resources their content needs
125    /// travel as whole records, each copied surface keeps its shown binding, and the
126    /// resource edges among them travel verbatim. A resource or resource pair this
127    /// graph already holds keeps this graph's truth. Edges leaving the component are
128    /// dropped (the snapshot is closed under the component).
129    /// Returns the [`ComponentCopy`]: the new keys plus the `source id → new id`
130    /// remap the host's facet-carry maps donor facets through (G4-R R0 — positions
131    /// and every other per-node character ride `arrangement.*` / `web.*` / … facets,
132    /// not the graph, so the fork's layout carry needs this mapping).
133    /// (Tear-out gestures G4.)
134    ///
135    /// [`component_members`]: Self::component_members
136    #[cfg(not(target_arch = "wasm32"))]
137    pub fn copy_component_from(
138        &mut self,
139        source: &Graph,
140        seed: Uuid,
141        source_graph: Option<String>,
142    ) -> ComponentCopy {
143        use petgraph::visit::{EdgeRef, IntoEdgeReferences};
144        let members = source.component_members(seed, &[]);
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(members.len());
149        let mut copy = ComponentCopy {
150            new_keys: Vec::with_capacity(members.len()),
151            id_remap: Vec::with_capacity(members.len()),
152        };
153        for (old_key, node) in members.iter().filter_map(|id| source.get_node_by_id(*id)) {
154            let source_id = node.id;
155            // Position is no longer a node field; the copy is placed by the
156            // destination's layout (seiche / arrangement facets), not carried over.
157            let new_key = self.copy_node_from(node, source_graph.clone(), Point2D::zero());
158            let new_id = self.inner.node(new_key).expect("inserted copy").id;
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(new_id, facet_id, value.clone(), &chartulary::AcceptAll)
171                        .expect("AcceptAll cannot reject copied content");
172                }
173            }
174            key_remap.insert(old_key, new_key);
175            copy.new_keys.push(new_key);
176            copy.id_remap.push((source_id, new_id));
177        }
178        // Re-point the component's internal surface edges (both endpoints copied):
179        // clone each edge's payload verbatim onto the new node pair.
180        for edge in source.inner.inner().edge_references() {
181            if let (Some(&from), Some(&to)) =
182                (key_remap.get(&edge.source()), key_remap.get(&edge.target()))
183            {
184                self.inner.connect(from, to, edge.weight().clone());
185            }
186        }
187        self.copy_component_resources(source, &key_remap);
188        self.bump_revision();
189        copy
190    }
191
192    /// The resource half of [`copy_component_from`](Self::copy_component_from):
193    /// records, shown bindings and resource edges for the copied surfaces.
194    #[cfg(not(target_arch = "wasm32"))]
195    fn copy_component_resources(
196        &mut self,
197        source: &Graph,
198        key_remap: &std::collections::HashMap<NodeKey, NodeKey>,
199    ) {
200        use super::predicate_declarations::PREDICATE_DECLARATIONS_FACET;
201        use super::resource_content::RESOURCE_PROPERTIES;
202        use petgraph::Direction;
203        use petgraph::visit::{EdgeRef, IntoEdgeReferences};
204        use std::collections::BTreeSet;
205
206        // The walked resources: every resource reachable from a copied surface's
207        // shown resource through resource edges (the walk `component_members` took).
208        let mut resources = BTreeSet::new();
209        let mut stack: Vec<Uuid> = key_remap
210            .keys()
211            .filter_map(|key| source.shown_resource_id(*key))
212            .filter(|id| source.resource(*id).is_some())
213            .collect();
214        while let Some(id) = stack.pop() {
215            if !resources.insert(id) {
216                continue;
217            }
218            let key = source
219                .resources
220                .key_of(&id)
221                .expect("walked resource exists");
222            for direction in [Direction::Outgoing, Direction::Incoming] {
223                for edge in source.resources.inner().edges_directed(key, direction) {
224                    let other = match direction {
225                        Direction::Outgoing => edge.target(),
226                        Direction::Incoming => edge.source(),
227                    };
228                    stack.push(source.resources.node(other).expect("endpoint").id());
229                }
230            }
231        }
232        // Declarations the copied statements and properties need, to a fixpoint
233        // (a declaration resource can itself carry declared properties).
234        let declarations = chartulary::FacetId::new(PREDICATE_DECLARATIONS_FACET);
235        let declared = |predicate: &str| {
236            let id = chartulary::resource_id_from_canonical_iri(predicate);
237            source
238                .resource_facets
239                .get(&id, &declarations)
240                .is_some()
241                .then_some(id)
242        };
243        let mut predicates: Vec<String> = source
244            .inner
245            .inner()
246            .edge_references()
247            .filter(|edge| {
248                key_remap.contains_key(&edge.source()) && key_remap.contains_key(&edge.target())
249            })
250            .flat_map(|edge| edge.weight().assertions())
251            .map(|statement| statement.predicate.clone())
252            .chain(
253                key_remap
254                    .keys()
255                    .flat_map(|key| source.node_properties(*key).unwrap_or_default())
256                    .map(|property| property.predicate),
257            )
258            .collect();
259        let properties = chartulary::FacetId::new(RESOURCE_PROPERTIES);
260        loop {
261            let before = resources.len();
262            for (from, to, payload) in source.resource_edges() {
263                if resources.contains(&from.id()) && resources.contains(&to.id()) {
264                    predicates.extend(
265                        payload
266                            .assertions()
267                            .iter()
268                            .map(|statement| statement.predicate.clone()),
269                    );
270                }
271            }
272            for id in &resources {
273                if let Some(value) = source.resource_facets.get(id, &properties) {
274                    predicates.extend(
275                        serde_json::from_value::<Vec<crate::types::NodeProperty>>(value.clone())
276                            .unwrap_or_default()
277                            .into_iter()
278                            .map(|property| property.predicate),
279                    );
280                }
281            }
282            let needed: Vec<Uuid> = predicates.drain(..).filter_map(|p| declared(&p)).collect();
283            resources.extend(needed);
284            if resources.len() == before {
285                break;
286            }
287        }
288        // Records first (a binding or edge needs its resource), then bindings, then
289        // resource edges. Truth this graph already holds wins.
290        for id in &resources {
291            if self.resource(*id).is_none() {
292                self.set_resource_record(*id, source.resource_record(*id));
293            }
294        }
295        for (old_key, new_key) in key_remap {
296            if let (Some(resource), Some(new_id)) = (
297                source.shown_resource_id(*old_key),
298                self.inner.node(*new_key).map(|node| node.id),
299            ) {
300                self.set_shown_resource(new_id, Some(resource));
301            }
302        }
303        let pairs: BTreeSet<(Uuid, Uuid)> = source
304            .resource_edges()
305            .map(|(from, to, _)| (from.id(), to.id()))
306            .filter(|(from, to)| resources.contains(from) && resources.contains(to))
307            .collect();
308        for (from, to) in pairs {
309            if self.persisted_resource_edges_between(from, to).is_empty() {
310                self.set_resource_edges_between(
311                    from,
312                    to,
313                    &source.persisted_resource_edges_between(from, to),
314                );
315            }
316        }
317    }
318}
319
320/// The result of [`Graph::copy_component_from`]: the minted keys plus the
321/// `(source id, new id)` pairs, in copy order. The id remap is the seam the
322/// host's facet-carry maps donor facets through (a forked node keeps its whole
323/// per-node character — `arrangement.*`, `web.*`, foreign namespaces — by
324/// copying facets from `source` to `new`).
325#[derive(Clone, Debug, Default)]
326pub struct ComponentCopy {
327    /// The fresh node keys in this graph, in copy order.
328    pub new_keys: Vec<NodeKey>,
329    /// `(source node id, minted node id)` per copied node, in copy order.
330    pub id_remap: Vec<(Uuid, Uuid)>,
331}
332
333#[cfg(all(test, not(target_arch = "wasm32")))]
334mod tests {
335    use super::*;
336    use std::collections::HashSet;
337
338    fn donor_with_content() -> (Graph, NodeKey) {
339        let mut a = Graph::new();
340        let key = a.add_node(
341            "https://example.com/article".to_string(),
342            Point2D::new(1.0, 2.0),
343        );
344        {
345            let node = a.inner.node_mut(key).unwrap();
346            node.title = "An Article".to_string();
347            node.tags = HashSet::from(["read-later".to_string(), "research".to_string()]);
348        }
349        a.append_node_property(
350            key,
351            crate::types::NodeProperty::new(
352                "https://schema.org/datePublished".to_string(),
353                "2026-01-01".to_string(),
354            ),
355        );
356        a.set_node_pinned(key, true);
357        (a, key)
358    }
359
360    #[test]
361    fn copy_mints_a_fresh_node_cloning_content_with_derivation() {
362        let (a, src_key) = donor_with_content();
363        let source = a.get_node(src_key).unwrap().clone();
364        let source_id = source.id;
365
366        let mut b = Graph::new();
367        let rev_before = b.revision();
368        let copy_key =
369            b.copy_node_from(&source, Some("graph-A".to_string()), Point2D::new(9.0, 9.0));
370        assert!(
371            b.revision() > rev_before,
372            "copying a node in is structural and advances the revision"
373        );
374        let copy = b.get_node(copy_key).unwrap();
375
376        // Fresh identity, content cloned.
377        assert_ne!(copy.id, source_id, "copy is a new entity");
378        assert_eq!(copy.title, "An Article");
379        assert_eq!(copy.tags, source.tags);
380        assert_eq!(copy.url(), source.url(), "same content, same address");
381
382        // Position is not a node field (not inherited, not carried); the copy is
383        // placed by the destination's layout.
384        assert_eq!(
385            b.node_is_pinned(copy_key),
386            Some(false),
387            "pin is per-placement"
388        );
389
390        // Derivation records the lineage back to the source.
391        let derivations = b.node_derivations(copy_key).unwrap();
392        assert_eq!(derivations.len(), 1);
393        let d = &derivations[0];
394        assert_eq!(d.sub_kind, ProvenanceSubKind::CopiedFrom);
395        assert_eq!(d.source_node, source_id.to_string());
396        assert_eq!(d.source_graph.as_deref(), Some("graph-A"));
397
398        // The copy is discoverable by its address in the destination index.
399        assert_eq!(b.get_nodes_by_url(source.url()).len(), 1);
400    }
401
402    #[test]
403    fn copy_does_not_carry_the_donor_import_provenance() {
404        let (mut a, src_key) = donor_with_content();
405        a.set_node_import_provenance(
406            src_key,
407            vec![crate::types::NodeImportProvenance {
408                source_id: "firefox".to_string(),
409                source_label: "Firefox bookmarks".to_string(),
410            }],
411        );
412        let source = a.get_node(src_key).unwrap().clone();
413
414        let mut b = Graph::new();
415        let copy_key = b.copy_node_from(&source, None, Point2D::zero());
416        let copy = b.get_node(copy_key).unwrap();
417
418        assert!(
419            b.node_import_provenance(copy_key).unwrap().is_empty(),
420            "donor import provenance is the donor's, not the copy's"
421        );
422        assert_eq!(
423            b.node_derivations(copy_key).unwrap()[0].source_graph,
424            None,
425            "same-graph / unknown source graph"
426        );
427    }
428
429    #[test]
430    fn copy_component_clones_the_connected_subgraph_with_edges_and_provenance() {
431        use crate::graph::{EdgeAssertion, SemanticSubKind};
432        let mut a = Graph::new();
433        let k1 = a.add_node("https://a.com/1".to_string(), Point2D::new(0.0, 0.0));
434        let k2 = a.add_node("https://a.com/2".to_string(), Point2D::new(1.0, 0.0));
435        let _k3 = a.add_node("https://a.com/3".to_string(), Point2D::new(9.0, 9.0)); // disconnected
436        a.assert_relation(
437            k1,
438            k2,
439            EdgeAssertion::Semantic {
440                // A Surface relation; the Resource case is the test below.
441                sub_kind: SemanticSubKind::UserGrouped,
442                label: None,
443            },
444        );
445        let seed = a.get_node(k1).unwrap().id;
446
447        let mut b = Graph::new();
448        let copy = b.copy_component_from(&a, seed, Some("graph-A".to_string()));
449
450        // The connected component is {k1, k2}; the disconnected k3 is not pulled in.
451        assert_eq!(
452            copy.new_keys.len(),
453            2,
454            "copied the 2-node component, not the lone disconnected node"
455        );
456        assert_eq!(b.nodes().count(), 2);
457        // The component's internal edge is re-pointed onto the copies.
458        assert_eq!(b.relations().count(), 1, "the internal edge is re-pointed");
459        // Each copy records `CopiedFrom` provenance back to the source graph.
460        for (key, _) in b.nodes() {
461            let derivations = b.node_derivations(key).unwrap();
462            assert_eq!(derivations.len(), 1);
463            assert_eq!(derivations[0].sub_kind, ProvenanceSubKind::CopiedFrom);
464            assert_eq!(derivations[0].source_graph.as_deref(), Some("graph-A"));
465        }
466        // The id remap pairs each source id with its minted copy's id — the seam
467        // the host's facet-carry maps donor facets through (G4-R R0).
468        assert_eq!(copy.id_remap.len(), 2);
469        for (source_id, new_id) in &copy.id_remap {
470            assert_ne!(source_id, new_id, "a copy is a new entity");
471            let (_, source_node) = a.get_node_by_id(*source_id).map(|(k, n)| (k, n)).unwrap();
472            let (_, new_node) = b.get_node_by_id(*new_id).map(|(k, n)| (k, n)).unwrap();
473            assert_eq!(source_node.url(), new_node.url(), "pairs align by content");
474            assert_eq!(
475                b.node_derivations(b.get_node_key_by_id(*new_id).unwrap())
476                    .unwrap()[0]
477                    .source_node,
478                source_id.to_string()
479            );
480        }
481    }
482
483    #[test]
484    fn copy_component_carries_a_resource_relation_whole() {
485        use crate::graph::{EdgeAssertion, SemanticSubKind};
486        let mut a = Graph::new();
487        let k1 = a.add_node("https://r.com/1".to_string(), Point2D::zero());
488        let k2 = a.add_node("https://r.com/2".to_string(), Point2D::zero());
489        let _k3 = a.add_node("https://r.com/3".to_string(), Point2D::zero()); // disconnected
490        a.assert_relation(
491            k1,
492            k2,
493            EdgeAssertion::Semantic {
494                sub_kind: SemanticSubKind::Hyperlink,
495                label: None,
496            },
497        );
498        // Precondition: the relation lives in the resource stratum only.
499        assert_eq!(a.edge_count(), 0, "no surface edge");
500        assert_eq!(a.resource_edges().count(), 1, "one resource edge");
501        assert_eq!(
502            a.weakly_connected_components().len(),
503            3,
504            "the surface partition cannot see the relation"
505        );
506        let seed = a.get_node(k1).unwrap().id;
507
508        let mut b = Graph::new();
509        let copy = b.copy_component_from(&a, seed, None);
510
511        assert_eq!(
512            copy.new_keys.len(),
513            2,
514            "the resource-joined pair copies whole"
515        );
516        assert_eq!(b.nodes().count(), 2);
517        // Bindings carried: each copy shows its donor's resource (ids retained).
518        for (source_id, new_id) in &copy.id_remap {
519            let source_key = a.get_node_key_by_id(*source_id).unwrap();
520            let new_key = b.get_node_key_by_id(*new_id).unwrap();
521            let resource = a.shown_resource_id(source_key).expect("donor binding");
522            assert_eq!(b.shown_resource_id(new_key), Some(resource));
523            assert_eq!(b.resource_record(resource), a.resource_record(resource));
524        }
525        // The relation is present in the copy, verbatim, between the new surfaces.
526        let donor_edges: Vec<_> = a
527            .resource_edges()
528            .map(|(f, t, p)| (f.id(), t.id(), p.clone()))
529            .collect();
530        let copied_edges: Vec<_> = b
531            .resource_edges()
532            .map(|(f, t, p)| (f.id(), t.id(), p.clone()))
533            .collect();
534        assert_eq!(
535            copied_edges, donor_edges,
536            "the resource edge travels verbatim"
537        );
538        let projected: Vec<_> = b.projected_relations().map(|(_, row)| row).collect();
539        assert_eq!(
540            projected.len(),
541            1,
542            "the relation projects between the copies"
543        );
544        let ids: HashSet<_> = copy.id_remap.iter().map(|(_, new)| *new).collect();
545        let from = b.get_node(projected[0].from).unwrap().id;
546        let to = b.get_node(projected[0].to).unwrap().id;
547        assert!(ids.contains(&from) && ids.contains(&to) && from != to);
548        assert_eq!(
549            b.component_members(copy.id_remap[0].1, &[]).len(),
550            2,
551            "the copy is one component in its own graph"
552        );
553    }
554}