graph-traversal.go raw
1 //go:build !(js && wasm)
2
3 package database
4
5 import (
6 "bytes"
7 "errors"
8
9 "github.com/dgraph-io/badger/v4"
10 "next.orly.dev/pkg/lol/chk"
11 "next.orly.dev/pkg/lol/log"
12 "next.orly.dev/pkg/database/indexes"
13 "next.orly.dev/pkg/database/indexes/types"
14 "next.orly.dev/pkg/nostr/encoders/hex"
15 )
16
17 // Graph traversal errors
18 var (
19 ErrPubkeyNotFound = errors.New("pubkey not found in database")
20 ErrEventNotFound = errors.New("event not found in database")
21 )
22
23 // GetPTagsFromEventSerial extracts p-tag pubkey serials from an event by its serial.
24 // This is a pure index-based operation - no event decoding required.
25 // It scans the epg (event-pubkey-graph) index for p-tag edges.
26 func (d *D) GetPTagsFromEventSerial(eventSerial *types.Uint40) ([]*types.Uint40, error) {
27 var pubkeySerials []*types.Uint40
28
29 // Build prefix: epg|event_serial
30 prefix := new(bytes.Buffer)
31 prefix.Write([]byte(indexes.EventPubkeyGraphPrefix))
32 if err := eventSerial.MarshalWrite(prefix); chk.E(err) {
33 return nil, err
34 }
35 searchPrefix := prefix.Bytes()
36
37 err := d.View(func(txn *badger.Txn) error {
38 opts := badger.DefaultIteratorOptions
39 opts.PrefetchValues = false
40 opts.Prefix = searchPrefix
41
42 it := txn.NewIterator(opts)
43 defer it.Close()
44
45 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
46 key := it.Item().KeyCopy(nil)
47
48 // Decode key: epg(3)|event_serial(5)|pubkey_serial(5)|kind(2)|direction(1)
49 if len(key) != 16 {
50 continue
51 }
52
53 // Extract direction to filter for p-tags only
54 direction := key[15]
55 if direction != types.EdgeDirectionPTagOut {
56 continue // Skip author edges, only want p-tag edges
57 }
58
59 // Extract pubkey serial (bytes 8-12)
60 pubkeySerial := new(types.Uint40)
61 serialReader := bytes.NewReader(key[8:13])
62 if err := pubkeySerial.UnmarshalRead(serialReader); chk.E(err) {
63 continue
64 }
65
66 pubkeySerials = append(pubkeySerials, pubkeySerial)
67 }
68 return nil
69 })
70
71 return pubkeySerials, err
72 }
73
74 // GetETagsFromEventSerial extracts e-tag event serials from an event by its serial.
75 // This is a pure index-based operation - no event decoding required.
76 // It scans the eeg (event-event-graph) index for outbound e-tag edges.
77 func (d *D) GetETagsFromEventSerial(eventSerial *types.Uint40) ([]*types.Uint40, error) {
78 var targetSerials []*types.Uint40
79
80 // Build prefix: eeg|source_event_serial
81 prefix := new(bytes.Buffer)
82 prefix.Write([]byte(indexes.EventEventGraphPrefix))
83 if err := eventSerial.MarshalWrite(prefix); chk.E(err) {
84 return nil, err
85 }
86 searchPrefix := prefix.Bytes()
87
88 err := d.View(func(txn *badger.Txn) error {
89 opts := badger.DefaultIteratorOptions
90 opts.PrefetchValues = false
91 opts.Prefix = searchPrefix
92
93 it := txn.NewIterator(opts)
94 defer it.Close()
95
96 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
97 key := it.Item().KeyCopy(nil)
98
99 // Decode key: eeg(3)|source_serial(5)|target_serial(5)|kind(2)|direction(1)
100 if len(key) != 16 {
101 continue
102 }
103
104 // Extract target serial (bytes 8-12)
105 targetSerial := new(types.Uint40)
106 serialReader := bytes.NewReader(key[8:13])
107 if err := targetSerial.UnmarshalRead(serialReader); chk.E(err) {
108 continue
109 }
110
111 targetSerials = append(targetSerials, targetSerial)
112 }
113 return nil
114 })
115
116 return targetSerials, err
117 }
118
119 // GetReferencingEvents finds all events that reference a target event via e-tags.
120 // Optionally filters by event kinds. Uses the gee (reverse e-tag graph) index.
121 func (d *D) GetReferencingEvents(targetSerial *types.Uint40, kinds []uint16) ([]*types.Uint40, error) {
122 var sourceSerials []*types.Uint40
123
124 if len(kinds) == 0 {
125 // No kind filter - scan all kinds
126 prefix := new(bytes.Buffer)
127 prefix.Write([]byte(indexes.GraphEventEventPrefix))
128 if err := targetSerial.MarshalWrite(prefix); chk.E(err) {
129 return nil, err
130 }
131 searchPrefix := prefix.Bytes()
132
133 err := d.View(func(txn *badger.Txn) error {
134 opts := badger.DefaultIteratorOptions
135 opts.PrefetchValues = false
136 opts.Prefix = searchPrefix
137
138 it := txn.NewIterator(opts)
139 defer it.Close()
140
141 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
142 key := it.Item().KeyCopy(nil)
143
144 // Decode key: gee(3)|target_serial(5)|kind(2)|direction(1)|source_serial(5)
145 if len(key) != 16 {
146 continue
147 }
148
149 // Extract source serial (bytes 11-15)
150 sourceSerial := new(types.Uint40)
151 serialReader := bytes.NewReader(key[11:16])
152 if err := sourceSerial.UnmarshalRead(serialReader); chk.E(err) {
153 continue
154 }
155
156 sourceSerials = append(sourceSerials, sourceSerial)
157 }
158 return nil
159 })
160 return sourceSerials, err
161 }
162
163 // With kind filter - scan each kind's prefix
164 for _, k := range kinds {
165 kind := new(types.Uint16)
166 kind.Set(k)
167
168 direction := new(types.Letter)
169 direction.Set(types.EdgeDirectionETagIn)
170
171 prefix := new(bytes.Buffer)
172 if err := indexes.GraphEventEventEnc(targetSerial, kind, direction, nil).MarshalWrite(prefix); chk.E(err) {
173 return nil, err
174 }
175 searchPrefix := prefix.Bytes()
176
177 err := d.View(func(txn *badger.Txn) error {
178 opts := badger.DefaultIteratorOptions
179 opts.PrefetchValues = false
180 opts.Prefix = searchPrefix
181
182 it := txn.NewIterator(opts)
183 defer it.Close()
184
185 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
186 key := it.Item().KeyCopy(nil)
187
188 // Extract source serial (last 5 bytes)
189 if len(key) < 5 {
190 continue
191 }
192 sourceSerial := new(types.Uint40)
193 serialReader := bytes.NewReader(key[len(key)-5:])
194 if err := sourceSerial.UnmarshalRead(serialReader); chk.E(err) {
195 continue
196 }
197
198 sourceSerials = append(sourceSerials, sourceSerial)
199 }
200 return nil
201 })
202 if chk.E(err) {
203 return nil, err
204 }
205 }
206
207 return sourceSerials, nil
208 }
209
210 // FindEventByAuthorAndKind finds the most recent event of a specific kind by an author.
211 // This is used to find kind-3 contact lists for follow graph traversal.
212 // Returns nil, nil if no matching event is found.
213 func (d *D) FindEventByAuthorAndKind(authorSerial *types.Uint40, kind uint16) (*types.Uint40, error) {
214 var eventSerial *types.Uint40
215
216 // First, get the full pubkey from the serial
217 pubkey, err := d.GetPubkeyBySerial(authorSerial)
218 if err != nil {
219 return nil, err
220 }
221
222 // Build prefix for kind-pubkey index: kpc|kind|pubkey_hash
223 pubHash := new(types.PubHash)
224 if err := pubHash.FromPubkey(pubkey); chk.E(err) {
225 return nil, err
226 }
227
228 kindType := new(types.Uint16)
229 kindType.Set(kind)
230
231 prefix := new(bytes.Buffer)
232 prefix.Write([]byte(indexes.KindPubkeyPrefix))
233 if err := kindType.MarshalWrite(prefix); chk.E(err) {
234 return nil, err
235 }
236 if err := pubHash.MarshalWrite(prefix); chk.E(err) {
237 return nil, err
238 }
239 searchPrefix := prefix.Bytes()
240
241 err = d.View(func(txn *badger.Txn) error {
242 opts := badger.DefaultIteratorOptions
243 opts.PrefetchValues = false
244 opts.Prefix = searchPrefix
245 opts.Reverse = true // Most recent first (highest created_at)
246
247 it := txn.NewIterator(opts)
248 defer it.Close()
249
250 // Seek to end of prefix range for reverse iteration
251 seekKey := make([]byte, len(searchPrefix)+8+5) // prefix + max timestamp + max serial
252 copy(seekKey, searchPrefix)
253 for i := len(searchPrefix); i < len(seekKey); i++ {
254 seekKey[i] = 0xFF
255 }
256
257 it.Seek(seekKey)
258 if !it.ValidForPrefix(searchPrefix) {
259 // Try going to the first valid key if seek went past
260 it.Rewind()
261 it.Seek(searchPrefix)
262 }
263
264 if it.ValidForPrefix(searchPrefix) {
265 key := it.Item().KeyCopy(nil)
266
267 // Decode key: kpc(3)|kind(2)|pubkey_hash(8)|created_at(8)|serial(5)
268 // Total: 26 bytes
269 if len(key) < 26 {
270 return nil
271 }
272
273 // Extract serial (last 5 bytes)
274 eventSerial = new(types.Uint40)
275 serialReader := bytes.NewReader(key[len(key)-5:])
276 if err := eventSerial.UnmarshalRead(serialReader); chk.E(err) {
277 return err
278 }
279 }
280 return nil
281 })
282
283 return eventSerial, err
284 }
285
286 // GetPubkeyHexFromSerial converts a pubkey serial to its hex string representation.
287 func (d *D) GetPubkeyHexFromSerial(serial *types.Uint40) (string, error) {
288 pubkey, err := d.GetPubkeyBySerial(serial)
289 if err != nil {
290 return "", err
291 }
292 return hex.Enc(pubkey), nil
293 }
294
295 // GetEventIDFromSerial converts an event serial to its hex ID string.
296 func (d *D) GetEventIDFromSerial(serial *types.Uint40) (string, error) {
297 eventID, err := d.GetEventIdBySerial(serial)
298 if err != nil {
299 return "", err
300 }
301 return hex.Enc(eventID), nil
302 }
303
304 // GetEventsReferencingPubkey finds all events that reference a pubkey via p-tags.
305 // Uses the peg (pubkey-event-graph) index with direction filter for inbound p-tags.
306 // Optionally filters by event kinds.
307 func (d *D) GetEventsReferencingPubkey(pubkeySerial *types.Uint40, kinds []uint16) ([]*types.Uint40, error) {
308 var eventSerials []*types.Uint40
309
310 if len(kinds) == 0 {
311 // No kind filter - we need to scan common kinds since direction comes after kind in the key
312 // Use same approach as QueryPTagGraph
313 commonKinds := []uint16{1, 6, 7, 9735, 10002, 3, 4, 5, 30023}
314 kinds = commonKinds
315 }
316
317 for _, k := range kinds {
318 kind := new(types.Uint16)
319 kind.Set(k)
320
321 direction := new(types.Letter)
322 direction.Set(types.EdgeDirectionPTagIn) // Inbound p-tags
323
324 prefix := new(bytes.Buffer)
325 if err := indexes.PubkeyEventGraphEnc(pubkeySerial, kind, direction, nil).MarshalWrite(prefix); chk.E(err) {
326 return nil, err
327 }
328 searchPrefix := prefix.Bytes()
329
330 err := d.View(func(txn *badger.Txn) error {
331 opts := badger.DefaultIteratorOptions
332 opts.PrefetchValues = false
333 opts.Prefix = searchPrefix
334
335 it := txn.NewIterator(opts)
336 defer it.Close()
337
338 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
339 key := it.Item().KeyCopy(nil)
340
341 // Key format: peg(3)|pubkey_serial(5)|kind(2)|direction(1)|event_serial(5) = 16 bytes
342 if len(key) != 16 {
343 continue
344 }
345
346 // Extract event serial (last 5 bytes)
347 eventSerial := new(types.Uint40)
348 serialReader := bytes.NewReader(key[11:16])
349 if err := eventSerial.UnmarshalRead(serialReader); chk.E(err) {
350 continue
351 }
352
353 eventSerials = append(eventSerials, eventSerial)
354 }
355 return nil
356 })
357 if chk.E(err) {
358 return nil, err
359 }
360 }
361
362 return eventSerials, nil
363 }
364
365 // GetEventsByAuthor finds all events authored by a pubkey.
366 // Uses the peg (pubkey-event-graph) index with direction filter for author edges.
367 // Optionally filters by event kinds.
368 func (d *D) GetEventsByAuthor(authorSerial *types.Uint40, kinds []uint16) ([]*types.Uint40, error) {
369 var eventSerials []*types.Uint40
370
371 if len(kinds) == 0 {
372 // No kind filter - scan for author direction across common kinds
373 // This is less efficient but necessary without kind filter
374 commonKinds := []uint16{0, 1, 3, 6, 7, 30023, 10002}
375 kinds = commonKinds
376 }
377
378 for _, k := range kinds {
379 kind := new(types.Uint16)
380 kind.Set(k)
381
382 direction := new(types.Letter)
383 direction.Set(types.EdgeDirectionAuthor) // Author edges
384
385 prefix := new(bytes.Buffer)
386 if err := indexes.PubkeyEventGraphEnc(authorSerial, kind, direction, nil).MarshalWrite(prefix); chk.E(err) {
387 return nil, err
388 }
389 searchPrefix := prefix.Bytes()
390
391 err := d.View(func(txn *badger.Txn) error {
392 opts := badger.DefaultIteratorOptions
393 opts.PrefetchValues = false
394 opts.Prefix = searchPrefix
395
396 it := txn.NewIterator(opts)
397 defer it.Close()
398
399 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
400 key := it.Item().KeyCopy(nil)
401
402 // Key format: peg(3)|pubkey_serial(5)|kind(2)|direction(1)|event_serial(5) = 16 bytes
403 if len(key) != 16 {
404 continue
405 }
406
407 // Extract event serial (last 5 bytes)
408 eventSerial := new(types.Uint40)
409 serialReader := bytes.NewReader(key[11:16])
410 if err := eventSerial.UnmarshalRead(serialReader); chk.E(err) {
411 continue
412 }
413
414 eventSerials = append(eventSerials, eventSerial)
415 }
416 return nil
417 })
418 if chk.E(err) {
419 return nil, err
420 }
421 }
422
423 return eventSerials, nil
424 }
425
426 // GetFollowsFromPubkeySerial returns the pubkey serials that a user follows.
427 // This extracts p-tags from the user's kind-3 contact list event.
428 // Returns an empty slice if no kind-3 event is found.
429 func (d *D) GetFollowsFromPubkeySerial(pubkeySerial *types.Uint40) ([]*types.Uint40, error) {
430 // Find the kind-3 event for this pubkey
431 contactEventSerial, err := d.FindEventByAuthorAndKind(pubkeySerial, 3)
432 if err != nil {
433 log.D.F("GetFollowsFromPubkeySerial: error finding kind-3 for serial %d: %v", pubkeySerial.Get(), err)
434 return nil, nil // No kind-3 event found is not an error
435 }
436 if contactEventSerial == nil {
437 log.T.F("GetFollowsFromPubkeySerial: no kind-3 event found for serial %d", pubkeySerial.Get())
438 return nil, nil
439 }
440
441 // Extract p-tags from the contact list event
442 follows, err := d.GetPTagsFromEventSerial(contactEventSerial)
443 if err != nil {
444 return nil, err
445 }
446
447 log.T.F("GetFollowsFromPubkeySerial: found %d follows for serial %d", len(follows), pubkeySerial.Get())
448 return follows, nil
449 }
450
451 // GetFollowersOfPubkeySerial returns the pubkey serials of users who follow a given pubkey.
452 // This finds all kind-3 events that have a p-tag referencing the target pubkey.
453 func (d *D) GetFollowersOfPubkeySerial(targetSerial *types.Uint40) ([]*types.Uint40, error) {
454 // Find all kind-3 events that reference this pubkey via p-tag
455 kind3Events, err := d.GetEventsReferencingPubkey(targetSerial, []uint16{3})
456 if err != nil {
457 return nil, err
458 }
459
460 // Extract the author serials from these events
461 var followerSerials []*types.Uint40
462 seen := make(map[uint64]bool)
463
464 for _, eventSerial := range kind3Events {
465 // Get the author of this kind-3 event
466 // We need to look up the event to get its author
467 // Use the epg index to find the author edge
468 authorSerial, err := d.GetEventAuthorSerial(eventSerial)
469 if err != nil {
470 log.D.F("GetFollowersOfPubkeySerial: couldn't get author for event %d: %v", eventSerial.Get(), err)
471 continue
472 }
473
474 // Deduplicate (a user might have multiple kind-3 events)
475 if seen[authorSerial.Get()] {
476 continue
477 }
478 seen[authorSerial.Get()] = true
479 followerSerials = append(followerSerials, authorSerial)
480 }
481
482 log.T.F("GetFollowersOfPubkeySerial: found %d followers for serial %d", len(followerSerials), targetSerial.Get())
483 return followerSerials, nil
484 }
485
486 // GetEventAuthorSerial finds the author pubkey serial for an event.
487 // Uses the epg (event-pubkey-graph) index with author direction.
488 func (d *D) GetEventAuthorSerial(eventSerial *types.Uint40) (*types.Uint40, error) {
489 var authorSerial *types.Uint40
490
491 // Build prefix: epg|event_serial
492 prefix := new(bytes.Buffer)
493 prefix.Write([]byte(indexes.EventPubkeyGraphPrefix))
494 if err := eventSerial.MarshalWrite(prefix); chk.E(err) {
495 return nil, err
496 }
497 searchPrefix := prefix.Bytes()
498
499 err := d.View(func(txn *badger.Txn) error {
500 opts := badger.DefaultIteratorOptions
501 opts.PrefetchValues = false
502 opts.Prefix = searchPrefix
503
504 it := txn.NewIterator(opts)
505 defer it.Close()
506
507 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
508 key := it.Item().KeyCopy(nil)
509
510 // Decode key: epg(3)|event_serial(5)|pubkey_serial(5)|kind(2)|direction(1)
511 if len(key) != 16 {
512 continue
513 }
514
515 // Check direction - we want author (0)
516 direction := key[15]
517 if direction != types.EdgeDirectionAuthor {
518 continue
519 }
520
521 // Extract pubkey serial (bytes 8-12)
522 authorSerial = new(types.Uint40)
523 serialReader := bytes.NewReader(key[8:13])
524 if err := authorSerial.UnmarshalRead(serialReader); chk.E(err) {
525 continue
526 }
527
528 return nil // Found the author
529 }
530 return ErrEventNotFound
531 })
532
533 return authorSerial, err
534 }
535
536 // GetFollowsViaPPG returns pubkey serials that the source pubkey references via the
537 // ppg (pubkey-pubkey-graph) materialized index. This is a single prefix scan that
538 // replaces the two-hop GetFollowsFromPubkeySerial (find kind-3 → extract p-tags).
539 //
540 // Key format: ppg(3)|source(5)|target(5)|kind(2)|direction(1)|event(5) = 21 bytes
541 // We scan prefix ppg|source and extract target serials at offset 8..13.
542 func (d *D) GetFollowsViaPPG(sourceSerial *types.Uint40) ([]*types.Uint40, error) {
543 var targets []*types.Uint40
544
545 prefix := new(bytes.Buffer)
546 prefix.Write([]byte(indexes.PubkeyPubkeyGraphPrefix))
547 if err := sourceSerial.MarshalWrite(prefix); chk.E(err) {
548 return nil, err
549 }
550 searchPrefix := prefix.Bytes()
551
552 err := d.View(func(txn *badger.Txn) error {
553 opts := badger.DefaultIteratorOptions
554 opts.PrefetchValues = false
555 opts.Prefix = searchPrefix
556
557 it := txn.NewIterator(opts)
558 defer it.Close()
559
560 seen := make(map[uint64]bool)
561 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
562 key := it.Item().KeyCopy(nil)
563 if len(key) != 21 {
564 continue
565 }
566 // Extract target pubkey serial at bytes 8..13
567 target := new(types.Uint40)
568 if err := target.UnmarshalRead(bytes.NewReader(key[8:13])); chk.E(err) {
569 continue
570 }
571 if seen[target.Get()] {
572 continue
573 }
574 seen[target.Get()] = true
575 targets = append(targets, target)
576 }
577 return nil
578 })
579 return targets, err
580 }
581
582 // GetFollowersViaGPP returns pubkey serials that reference the target pubkey via the
583 // gpp (graph-pubkey-pubkey) reverse index. This is a single prefix scan that replaces
584 // the three-hop GetFollowersOfPubkeySerial (find referencing events → get authors → dedup).
585 //
586 // Key format: gpp(3)|target(5)|kind(2)|direction(1)|source(5)|event(5) = 21 bytes
587 // For kind-3 followers, we can optionally narrow with kind filter.
588 func (d *D) GetFollowersViaGPP(targetSerial *types.Uint40) ([]*types.Uint40, error) {
589 var sources []*types.Uint40
590
591 prefix := new(bytes.Buffer)
592 prefix.Write([]byte(indexes.GraphPubkeyPubkeyPrefix))
593 if err := targetSerial.MarshalWrite(prefix); chk.E(err) {
594 return nil, err
595 }
596 searchPrefix := prefix.Bytes()
597
598 err := d.View(func(txn *badger.Txn) error {
599 opts := badger.DefaultIteratorOptions
600 opts.PrefetchValues = false
601 opts.Prefix = searchPrefix
602
603 it := txn.NewIterator(opts)
604 defer it.Close()
605
606 seen := make(map[uint64]bool)
607 for it.Seek(searchPrefix); it.ValidForPrefix(searchPrefix); it.Next() {
608 key := it.Item().KeyCopy(nil)
609 if len(key) != 21 {
610 continue
611 }
612 // Extract source pubkey serial at bytes 11..16
613 source := new(types.Uint40)
614 if err := source.UnmarshalRead(bytes.NewReader(key[11:16])); chk.E(err) {
615 continue
616 }
617 if seen[source.Get()] {
618 continue
619 }
620 seen[source.Get()] = true
621 sources = append(sources, source)
622 }
623 return nil
624 })
625 return sources, err
626 }
627
628 // PubkeyHexToSerial converts a pubkey hex string to its serial, if it exists.
629 // Returns an error if the pubkey is not in the database.
630 func (d *D) PubkeyHexToSerial(pubkeyHex string) (*types.Uint40, error) {
631 pubkeyBytes, err := hex.Dec(pubkeyHex)
632 if err != nil {
633 return nil, err
634 }
635 if len(pubkeyBytes) != 32 {
636 return nil, errors.New("invalid pubkey length")
637 }
638 return d.GetPubkeySerial(pubkeyBytes)
639 }
640
641 // EventIDHexToSerial converts an event ID hex string to its serial, if it exists.
642 // Returns an error if the event is not in the database.
643 func (d *D) EventIDHexToSerial(eventIDHex string) (*types.Uint40, error) {
644 eventIDBytes, err := hex.Dec(eventIDHex)
645 if err != nil {
646 return nil, err
647 }
648 if len(eventIDBytes) != 32 {
649 return nil, errors.New("invalid event ID length")
650 }
651 return d.GetSerialById(eventIDBytes)
652 }
653