graph_test.go raw
1 package store
2
3 import (
4 "os"
5 "path/filepath"
6 "reflect"
7 "sort"
8 "testing"
9
10 "git.smesh.lol/torly/pkg/nostr"
11 )
12
13 func pubkeyOf(t *testing.T, seed byte) string {
14 t.Helper()
15 pub := testKey(seed)
16 hex, err := nostr.PubKeyHex(pub)
17 if err != nil {
18 t.Fatal(err)
19 }
20 return hex
21 }
22
23 func graphQuery(seed string, depth int, edge, direction string) *nostr.GraphQuery {
24 return &nostr.GraphQuery{Seed: seed, Depth: depth, Edge: edge, Direction: direction}
25 }
26
27 func levelsEqual(t *testing.T, got, want [][]string) {
28 t.Helper()
29 for _, level := range got {
30 sort.Strings(level)
31 }
32 for _, level := range want {
33 sort.Strings(level)
34 }
35 if !reflect.DeepEqual(got, want) {
36 t.Fatalf("levels:\n got %v\nwant %v", got, want)
37 }
38 }
39
40 func TestGraphPubkeyPubkey(t *testing.T) {
41 e, _ := openTest(t)
42 alice, bob, carol, dave := pubkeyOf(t, 1), pubkeyOf(t, 2), pubkeyOf(t, 3), pubkeyOf(t, 4)
43
44 save(t, e, signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}, {"p", carol}}, ""))
45 save(t, e, signedEvent(t, 2, 3, 101, nostr.Tags{{"p", carol}}, ""))
46 save(t, e, signedEvent(t, 3, 3, 102, nostr.Tags{{"p", dave}}, ""))
47
48 res, err := e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
49 if err != nil {
50 t.Fatal(err)
51 }
52 levelsEqual(t, res.PubkeysByDepth, [][]string{{bob, carol}})
53 if res.TotalPubkeys != 2 || res.TotalEvents != 0 {
54 t.Fatalf("totals: %+v", res)
55 }
56
57 res, err = e.TraverseGraph(graphQuery(alice, 2, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
58 if err != nil {
59 t.Fatal(err)
60 }
61 levelsEqual(t, res.PubkeysByDepth, [][]string{{bob, carol}, {dave}})
62
63 res, err = e.TraverseGraph(graphQuery(carol, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirIn))
64 if err != nil {
65 t.Fatal(err)
66 }
67 levelsEqual(t, res.PubkeysByDepth, [][]string{{alice, bob}})
68
69 res, err = e.TraverseGraph(graphQuery(carol, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirBoth))
70 if err != nil {
71 t.Fatal(err)
72 }
73 levelsEqual(t, res.PubkeysByDepth, [][]string{{alice, bob, dave}})
74
75 // A missing seed is an empty result, not an error.
76 res, err = e.TraverseGraph(graphQuery(pubkeyOf(t, 99), 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
77 if err != nil || res.TotalPubkeys != 0 {
78 t.Fatalf("missing seed: %+v %v", res, err)
79 }
80 }
81
82 func TestGraphReplacementRemovesOldEdges(t *testing.T) {
83 e, _ := openTest(t)
84 alice, bob, carol := pubkeyOf(t, 1), pubkeyOf(t, 2), pubkeyOf(t, 3)
85 save(t, e, signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}}, ""))
86 save(t, e, signedEvent(t, 1, 3, 200, nostr.Tags{{"p", carol}}, ""))
87
88 res, err := e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
89 if err != nil {
90 t.Fatal(err)
91 }
92 levelsEqual(t, res.PubkeysByDepth, [][]string{{carol}})
93 }
94
95 func TestGraphPubkeyEvent(t *testing.T) {
96 e, _ := openTest(t)
97 alice := pubkeyOf(t, 1)
98 note := signedEvent(t, 1, 1, 100, nil, "alice note")
99 mention := signedEvent(t, 2, 1, 101, nostr.Tags{{"p", alice}, {"e", nostr.Hex(note.ID[:])}}, "hi alice")
100 save(t, e, note)
101 save(t, e, mention)
102
103 res, err := e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyEvent, nostr.GraphDirOut))
104 if err != nil {
105 t.Fatal(err)
106 }
107 levelsEqual(t, res.EventsByDepth, [][]string{{nostr.Hex(note.ID[:])}})
108
109 res, err = e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyEvent, nostr.GraphDirIn))
110 if err != nil {
111 t.Fatal(err)
112 }
113 levelsEqual(t, res.EventsByDepth, [][]string{{nostr.Hex(mention.ID[:])}})
114
115 res, err = e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyEvent, nostr.GraphDirBoth))
116 if err != nil {
117 t.Fatal(err)
118 }
119 levelsEqual(t, res.EventsByDepth, [][]string{{nostr.Hex(note.ID[:]), nostr.Hex(mention.ID[:])}})
120 }
121
122 func TestGraphThreadBackfillsOutOfOrderReplies(t *testing.T) {
123 e, _ := openTest(t)
124 alice, bob := pubkeyOf(t, 1), pubkeyOf(t, 2)
125 root := signedEvent(t, 1, 1, 100, nil, "root")
126 reply := signedEvent(t, 2, 1, 101, nostr.Tags{{"e", nostr.Hex(root.ID[:])}, {"p", alice}}, "reply")
127 deep := signedEvent(t, 3, 1, 102, nostr.Tags{{"e", nostr.Hex(reply.ID[:])}, {"p", bob}}, "deep reply")
128
129 // Save the chain in the worst possible order: the deepest reply first and
130 // the root last. The backfill must still connect both hops.
131 save(t, e, deep)
132 save(t, e, reply)
133 save(t, e, root)
134
135 res, err := e.TraverseGraph(graphQuery(alice, 3, nostr.GraphEdgeEventEvent, nostr.GraphDirBoth))
136 if err != nil {
137 t.Fatal(err)
138 }
139 levelsEqual(t, res.EventsByDepth, [][]string{
140 {nostr.Hex(reply.ID[:])},
141 {nostr.Hex(deep.ID[:])},
142 })
143
144 res, err = e.TraverseGraph(graphQuery(bob, 2, nostr.GraphEdgeEventEvent, nostr.GraphDirIn))
145 if err != nil {
146 t.Fatal(err)
147 }
148 levelsEqual(t, res.EventsByDepth, [][]string{{nostr.Hex(deep.ID[:])}})
149
150 // The authored roots themselves are not part of the result.
151 for _, level := range res.EventsByDepth {
152 for _, id := range level {
153 if id == nostr.Hex(root.ID[:]) || id == nostr.Hex(reply.ID[:]) {
154 t.Fatalf("root leaked into result: %v", res.EventsByDepth)
155 }
156 }
157 }
158 }
159
160 func TestGraphDeletionRemovesEdges(t *testing.T) {
161 e, _ := openTest(t)
162 bob := pubkeyOf(t, 2)
163 follow := signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}}, "")
164 save(t, e, follow)
165 if ok, err := e.Delete(follow.ID[:], follow.PubKey[:]); err != nil || !ok {
166 t.Fatalf("delete: %v %v", ok, err)
167 }
168 res, err := e.TraverseGraph(graphQuery(pubkeyOf(t, 1), 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
169 if err != nil {
170 t.Fatal(err)
171 }
172 if res.TotalPubkeys != 0 {
173 t.Fatalf("edges survived deletion: %+v", res)
174 }
175
176 root := signedEvent(t, 1, 1, 200, nil, "root")
177 reply := signedEvent(t, 2, 1, 201, nostr.Tags{{"e", nostr.Hex(root.ID[:])}}, "reply")
178 save(t, e, root)
179 save(t, e, reply)
180 if ok, err := e.Delete(root.ID[:], root.PubKey[:]); err != nil || !ok {
181 t.Fatalf("delete root: %v %v", ok, err)
182 }
183 res, err = e.TraverseGraph(graphQuery(pubkeyOf(t, 1), 2, nostr.GraphEdgeEventEvent, nostr.GraphDirBoth))
184 if err != nil {
185 t.Fatal(err)
186 }
187 if res.TotalEvents != 0 {
188 t.Fatalf("thread edges survived deletion: %+v", res)
189 }
190 }
191
192 func TestGraphSurvivesReopen(t *testing.T) {
193 e, dir := openTest(t)
194 alice, bob := pubkeyOf(t, 1), pubkeyOf(t, 2)
195 save(t, e, signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}}, ""))
196 if err := e.Flush(); err != nil {
197 t.Fatal(err)
198 }
199 if err := e.Close(); err != nil {
200 t.Fatal(err)
201 }
202
203 reopened, err := Open(dir, Options{})
204 if err != nil {
205 t.Fatal(err)
206 }
207 defer reopened.Close()
208 if err := reopened.RebuildGraph(); err != nil {
209 t.Fatal(err)
210 }
211 res, err := reopened.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
212 if err != nil {
213 t.Fatal(err)
214 }
215 levelsEqual(t, res.PubkeysByDepth, [][]string{{bob}})
216 }
217
218 func TestGraphRebuildStoreWithoutGraphIndexesExplicitly(t *testing.T) {
219 e, dir := openTest(t)
220 alice, bob := pubkeyOf(t, 1), pubkeyOf(t, 2)
221 save(t, e, signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}}, ""))
222 if err := e.Flush(); err != nil {
223 t.Fatal(err)
224 }
225 if err := e.Close(); err != nil {
226 t.Fatal(err)
227 }
228 for _, name := range []string{"pks", "spk", "epg", "peg", "eeg", "gee", "ppg", "gpp"} {
229 if err := os.Remove(filepath.Join(dir, "idx", name+".dat")); err != nil {
230 t.Fatal(err)
231 }
232 }
233 reopened, err := Open(dir, Options{})
234 if err != nil {
235 t.Fatal(err)
236 }
237 defer reopened.Close()
238 if err := reopened.RebuildGraph(); err != nil {
239 t.Fatal(err)
240 }
241 res, err := reopened.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
242 if err != nil {
243 t.Fatal(err)
244 }
245 levelsEqual(t, res.PubkeysByDepth, [][]string{{bob}})
246 }
247
248 func TestBulkImportRebuildGraph(t *testing.T) {
249 dir := t.TempDir()
250 e, err := Open(dir, Options{BulkImport: true})
251 if err != nil {
252 t.Fatal(err)
253 }
254 defer e.Close()
255 alice, bob, carol := pubkeyOf(t, 1), pubkeyOf(t, 2), pubkeyOf(t, 3)
256 save(t, e, signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}}, ""))
257 save(t, e, signedEvent(t, 1, 3, 200, nostr.Tags{{"p", carol}}, ""))
258
259 res, err := e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
260 if err != nil {
261 t.Fatal(err)
262 }
263 if res.TotalPubkeys != 0 {
264 t.Fatalf("graph was written during bulk import: %+v", res)
265 }
266 if err := e.RebuildGraph(); err != nil {
267 t.Fatal(err)
268 }
269 res, err = e.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
270 if err != nil {
271 t.Fatal(err)
272 }
273 levelsEqual(t, res.PubkeysByDepth, [][]string{{carol}})
274
275 all, err := e.Query(&nostr.Filter{})
276 if err != nil {
277 t.Fatal(err)
278 }
279 if len(all) != 1 {
280 t.Fatalf("bulk replacement kept %d events, want 1", len(all))
281 }
282 }
283
284 func TestBulkImportSeedsReplacementSlots(t *testing.T) {
285 dir := t.TempDir()
286 normal, err := Open(dir, Options{})
287 if err != nil {
288 t.Fatal(err)
289 }
290 alice, bob, carol := pubkeyOf(t, 1), pubkeyOf(t, 2), pubkeyOf(t, 3)
291 save(t, normal, signedEvent(t, 1, 3, 100, nostr.Tags{{"p", bob}}, ""))
292 if err := normal.Close(); err != nil {
293 t.Fatal(err)
294 }
295
296 bulk, err := Open(dir, Options{BulkImport: true})
297 if err != nil {
298 t.Fatal(err)
299 }
300 if ok, err := bulk.SaveEvent(signedEvent(t, 1, 3, 200, nostr.Tags{{"p", carol}}, "")); err != nil || !ok {
301 t.Fatalf("bulk replace: %v %v", ok, err)
302 }
303 if err := bulk.RebuildGraph(); err != nil {
304 t.Fatal(err)
305 }
306 all, err := bulk.Query(&nostr.Filter{})
307 if err != nil {
308 t.Fatal(err)
309 }
310 if len(all) != 1 {
311 t.Fatalf("replacement kept %d events, want 1", len(all))
312 }
313 res, err := bulk.TraverseGraph(graphQuery(alice, 1, nostr.GraphEdgePubkeyPubkey, nostr.GraphDirOut))
314 if err != nil {
315 t.Fatal(err)
316 }
317 levelsEqual(t, res.PubkeysByDepth, [][]string{{carol}})
318 if err := bulk.Close(); err != nil {
319 t.Fatal(err)
320 }
321 }
322