silk/
provenance.rs

1//! Read-only provenance observation.
2//!
3//! One primitive: `entries_affecting(id)`. Scans the OpLog and returns every
4//! entry whose payload references the given node or edge id, in topological
5//! order. Deterministic over OpLog state alone — see PROOF.md Theorem 5.
6//!
7//! Callers build typed provenance views on top of this. Silk does not bake
8//! in a `Provenance` taxonomy; the primitive is the contract.
9
10use std::collections::HashSet;
11
12use crate::entry::{Entry, GraphOp, Hash};
13use crate::oplog::OpLog;
14
15impl OpLog {
16    /// Return all entries whose payload references the given id (node_id or
17    /// edge_id, including edges whose source_id / target_id is `id`) in
18    /// topological order.
19    ///
20    /// Deterministic over OpLog state. Two peers with identical OpLogs return
21    /// byte-identical results. See PROOF.md Theorem 5.
22    ///
23    /// Post-compaction: pre-checkpoint writes are folded into a single
24    /// synthetic `Checkpoint` entry. If the checkpoint's embedded ops mention
25    /// `id`, the checkpoint entry itself is returned.
26    ///
27    /// Cost: linear scan over the OpLog. Unmeasured in practice; if this
28    /// becomes a hot path, add an id-indexed side table after profiling.
29    pub fn entries_affecting(&self, id: &str) -> Vec<&Entry> {
30        let mut matching: HashSet<Hash> = HashSet::new();
31        for (hash, entry) in self.iter_entries() {
32            if payload_mentions_id(&entry.payload, id) {
33                matching.insert(*hash);
34            }
35        }
36        self.topo_sort(&matching)
37    }
38}
39
40/// Does this op reference the given id (as a node_id, edge_id, source_id, or
41/// target_id)?  Recurses into Checkpoint ops so post-compaction scans still
42/// find matches.
43fn payload_mentions_id(op: &GraphOp, id: &str) -> bool {
44    match op {
45        GraphOp::AddNode { node_id, .. } => node_id == id,
46        GraphOp::AddEdge {
47            edge_id,
48            source_id,
49            target_id,
50            ..
51        } => edge_id == id || source_id == id || target_id == id,
52        GraphOp::UpdateProperty { entity_id, .. } => entity_id == id,
53        GraphOp::RemoveNode { node_id } => node_id == id,
54        GraphOp::RemoveEdge { edge_id } => edge_id == id,
55        GraphOp::DefineOntology { .. } => false,
56        GraphOp::ExtendOntology { .. } => false,
57        GraphOp::DefineLens { .. } => false,
58        GraphOp::Checkpoint { ops, .. } => ops.iter().any(|inner| payload_mentions_id(inner, id)),
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65    use crate::clock::LamportClock;
66    use crate::entry::{Entry, Value};
67    use crate::ontology::Ontology;
68
69    fn mk_genesis() -> Entry {
70        Entry::new(
71            GraphOp::DefineOntology {
72                ontology: Ontology {
73                    node_types: Default::default(),
74                    edge_types: Default::default(),
75                },
76            },
77            Vec::new(),
78            Vec::new(),
79            LamportClock::new("test-peer".to_string()),
80            "test-peer".to_string(),
81        )
82    }
83
84    fn mk_entry(op: GraphOp, parents: Vec<Hash>, clock: LamportClock) -> Entry {
85        Entry::new(op, parents, Vec::new(), clock, "test-peer".to_string())
86    }
87
88    fn add_node(id: &str) -> GraphOp {
89        GraphOp::AddNode {
90            node_id: id.to_string(),
91            node_type: "thing".to_string(),
92            subtype: None,
93            label: id.to_string(),
94            properties: Default::default(),
95        }
96    }
97
98    fn update_prop(id: &str, key: &str, value: &str) -> GraphOp {
99        GraphOp::UpdateProperty {
100            entity_id: id.to_string(),
101            key: key.to_string(),
102            value: Value::String(value.to_string()),
103        }
104    }
105
106    fn remove_node(id: &str) -> GraphOp {
107        GraphOp::RemoveNode {
108            node_id: id.to_string(),
109        }
110    }
111
112    fn add_edge(edge_id: &str, source_id: &str, target_id: &str) -> GraphOp {
113        GraphOp::AddEdge {
114            edge_id: edge_id.to_string(),
115            edge_type: "LINK".to_string(),
116            source_id: source_id.to_string(),
117            target_id: target_id.to_string(),
118            properties: Default::default(),
119        }
120    }
121
122    /// Test 7: never-existed id returns empty.
123    #[test]
124    fn never_existed_returns_empty() {
125        let log = OpLog::new(mk_genesis());
126        assert!(log.entries_affecting("nope").is_empty());
127    }
128
129    /// Test 1: single create returns the one entry.
130    #[test]
131    fn single_create_returns_one_entry() {
132        let mut log = OpLog::new(mk_genesis());
133        let mut clock = LamportClock::new("test-peer".to_string());
134        clock.tick();
135        let add = mk_entry(add_node("n1"), vec![log.heads()[0]], clock);
136        log.append(add.clone()).unwrap();
137
138        let result = log.entries_affecting("n1");
139        assert_eq!(result.len(), 1);
140        assert_eq!(result[0].hash, add.hash);
141    }
142
143    /// Test 2: many updates to same property return in topo order.
144    #[test]
145    fn many_updates_return_in_topo_order() {
146        let mut log = OpLog::new(mk_genesis());
147        let mut clock = LamportClock::new("test-peer".to_string());
148
149        clock.tick();
150        let add = mk_entry(add_node("n1"), vec![log.heads()[0]], clock.clone());
151        log.append(add.clone()).unwrap();
152
153        clock.tick();
154        let u1 = mk_entry(
155            update_prop("n1", "name", "foo"),
156            vec![add.hash],
157            clock.clone(),
158        );
159        log.append(u1.clone()).unwrap();
160
161        clock.tick();
162        let u2 = mk_entry(
163            update_prop("n1", "name", "bar"),
164            vec![u1.hash],
165            clock.clone(),
166        );
167        log.append(u2.clone()).unwrap();
168
169        let result = log.entries_affecting("n1");
170        assert_eq!(result.len(), 3);
171        assert_eq!(result[0].hash, add.hash);
172        assert_eq!(result[1].hash, u1.hash);
173        assert_eq!(result[2].hash, u2.hash);
174    }
175
176    /// Test 4: tombstoned node returns create + remove.
177    #[test]
178    fn tombstoned_node_returns_create_and_remove() {
179        let mut log = OpLog::new(mk_genesis());
180        let mut clock = LamportClock::new("test-peer".to_string());
181
182        clock.tick();
183        let add = mk_entry(add_node("n1"), vec![log.heads()[0]], clock.clone());
184        log.append(add.clone()).unwrap();
185
186        clock.tick();
187        let rm = mk_entry(remove_node("n1"), vec![add.hash], clock.clone());
188        log.append(rm.clone()).unwrap();
189
190        let result = log.entries_affecting("n1");
191        assert_eq!(result.len(), 2);
192        let hashes: Vec<Hash> = result.iter().map(|e| e.hash).collect();
193        assert!(hashes.contains(&add.hash));
194        assert!(hashes.contains(&rm.hash));
195    }
196
197    /// Test 5: node involved as edge source is found via edge lookup of node id.
198    /// Confirms edges whose source/target references the node DO surface.
199    #[test]
200    fn node_id_finds_edges_where_it_is_source_or_target() {
201        let mut log = OpLog::new(mk_genesis());
202        let mut clock = LamportClock::new("test-peer".to_string());
203
204        clock.tick();
205        let add_a = mk_entry(add_node("a"), vec![log.heads()[0]], clock.clone());
206        log.append(add_a.clone()).unwrap();
207        clock.tick();
208        let add_b = mk_entry(add_node("b"), vec![add_a.hash], clock.clone());
209        log.append(add_b.clone()).unwrap();
210        clock.tick();
211        let edge = mk_entry(add_edge("e1", "a", "b"), vec![add_b.hash], clock.clone());
212        log.append(edge.clone()).unwrap();
213
214        let for_a = log.entries_affecting("a");
215        let hashes_a: Vec<Hash> = for_a.iter().map(|e| e.hash).collect();
216        assert!(hashes_a.contains(&add_a.hash));
217        assert!(
218            hashes_a.contains(&edge.hash),
219            "edge with source=a should surface for node id 'a'"
220        );
221
222        let for_b = log.entries_affecting("b");
223        let hashes_b: Vec<Hash> = for_b.iter().map(|e| e.hash).collect();
224        assert!(hashes_b.contains(&add_b.hash));
225        assert!(
226            hashes_b.contains(&edge.hash),
227            "edge with target=b should surface for node id 'b'"
228        );
229    }
230
231    /// Test 6: edge id lookup returns AddEdge and subsequent ops.
232    #[test]
233    fn edge_id_lookup_returns_edge_ops() {
234        let mut log = OpLog::new(mk_genesis());
235        let mut clock = LamportClock::new("test-peer".to_string());
236
237        clock.tick();
238        let add_a = mk_entry(add_node("a"), vec![log.heads()[0]], clock.clone());
239        log.append(add_a.clone()).unwrap();
240        clock.tick();
241        let add_b = mk_entry(add_node("b"), vec![add_a.hash], clock.clone());
242        log.append(add_b.clone()).unwrap();
243        clock.tick();
244        let edge = mk_entry(add_edge("e1", "a", "b"), vec![add_b.hash], clock.clone());
245        log.append(edge.clone()).unwrap();
246        clock.tick();
247        let rm_edge = mk_entry(
248            GraphOp::RemoveEdge {
249                edge_id: "e1".to_string(),
250            },
251            vec![edge.hash],
252            clock.clone(),
253        );
254        log.append(rm_edge.clone()).unwrap();
255
256        let result = log.entries_affecting("e1");
257        let hashes: Vec<Hash> = result.iter().map(|e| e.hash).collect();
258        assert!(hashes.contains(&edge.hash));
259        assert!(hashes.contains(&rm_edge.hash));
260        assert_eq!(result.len(), 2, "only AddEdge and RemoveEdge reference e1");
261    }
262
263    /// Test 10: determinism — same ops on two peers produce identical results.
264    /// This validates Theorem 5's CRDT-safety corollary. Clocks fixed to
265    /// simulate byte-identical OpLogs on two peers after sync.
266    #[test]
267    fn determinism_two_peers_identical_results() {
268        let build_log = || {
269            let genesis = Entry::new(
270                GraphOp::DefineOntology {
271                    ontology: Ontology {
272                        node_types: Default::default(),
273                        edge_types: Default::default(),
274                    },
275                },
276                Vec::new(),
277                Vec::new(),
278                LamportClock::with_values("peer", 1000, 0),
279                "peer".to_string(),
280            );
281            let mut log = OpLog::new(genesis);
282            let add = mk_entry(
283                add_node("n1"),
284                vec![log.heads()[0]],
285                LamportClock::with_values("peer", 1001, 0),
286            );
287            log.append(add.clone()).unwrap();
288            let u1 = mk_entry(
289                update_prop("n1", "x", "1"),
290                vec![add.hash],
291                LamportClock::with_values("peer", 1002, 0),
292            );
293            log.append(u1.clone()).unwrap();
294            let u2 = mk_entry(
295                update_prop("n1", "y", "2"),
296                vec![u1.hash],
297                LamportClock::with_values("peer", 1003, 0),
298            );
299            log.append(u2.clone()).unwrap();
300            log
301        };
302
303        let log_a = build_log();
304        let log_b = build_log();
305
306        let a: Vec<Hash> = log_a
307            .entries_affecting("n1")
308            .iter()
309            .map(|e| e.hash)
310            .collect();
311        let b: Vec<Hash> = log_b
312            .entries_affecting("n1")
313            .iter()
314            .map(|e| e.hash)
315            .collect();
316        assert_eq!(a, b, "deterministic output across peers (Theorem 5)");
317    }
318}
silk/provenance.rs

silk/
provenance.rs
