graph.go raw
1 package nostr
2
3 import (
4 "errors"
5 "sort"
6 "strconv"
7 "strings"
8 )
9
10 // Graph query edge families. They mirror orly's graph extension: pp is the
11 // pubkey↔pubkey graph, pe the pubkey↔event bipartite graph, and ee the
12 // event↔event thread graph.
13 const (
14 GraphEdgePubkeyPubkey = "pp"
15 GraphEdgePubkeyEvent = "pe"
16 GraphEdgeEventEvent = "ee"
17 )
18
19 // Graph directions.
20 const (
21 GraphDirOut = "out"
22 GraphDirIn = "in"
23 GraphDirBoth = "both"
24 )
25
26 // GraphMaxDepth is the largest accepted traversal depth.
27 const GraphMaxDepth = 16
28
29 // KindGraphResult is the relay-signed event kind returned for a _graph query.
30 const KindGraphResult = 39000
31
32 var (
33 errGraphSeed = errors.New("graph: seed must be 64 hexadecimal characters")
34 errGraphDepth = errors.New("graph: depth must be between 1 and 16")
35 errGraphEdge = errors.New("graph: edge must be pp, pe or ee")
36 errGraphDirection = errors.New("graph: direction must be out, in or both")
37 )
38
39 // GraphQuery is the parsed value of a filter's _graph extension.
40 //
41 // The canonical wire form is a four-element array:
42 //
43 // ["_graph", ["<pubkey>", <depth>, "<edge>", "<direction>"]]
44 //
45 // The object form accepted by orly is also decoded:
46 //
47 // {"pubkey":"<pubkey>","depth":1,"edge":"pp","direction":"out"}
48 type GraphQuery struct {
49 Seed string
50 Depth int
51 Edge string
52 Direction string
53 }
54
55 // Validate checks a normalized graph query without changing it.
56 func (q *GraphQuery) Validate() error {
57 if q == nil {
58 return errors.New("graph: nil query")
59 }
60 if !IsHex64(q.Seed) {
61 return errGraphSeed
62 }
63 if q.Depth < 1 || q.Depth > GraphMaxDepth {
64 return errGraphDepth
65 }
66 switch q.Edge {
67 case GraphEdgePubkeyPubkey, GraphEdgePubkeyEvent, GraphEdgeEventEvent:
68 default:
69 return errGraphEdge
70 }
71 switch q.Direction {
72 case GraphDirOut, GraphDirIn, GraphDirBoth:
73 default:
74 return errGraphDirection
75 }
76 return nil
77 }
78
79 // normalize applies the defaults and canonical spelling the decoder promises:
80 // a lowercase seed, depth 1 when omitted, and lowercase edge/direction names.
81 func (q *GraphQuery) normalize() error {
82 q.Seed = strings.ToLower(q.Seed)
83 q.Edge = strings.ToLower(q.Edge)
84 q.Direction = strings.ToLower(q.Direction)
85 if q.Depth == 0 {
86 q.Depth = 1
87 }
88 return q.Validate()
89 }
90
91 // IsOutbound reports whether traversal follows outbound edges.
92 func (q *GraphQuery) IsOutbound() bool {
93 return q.Direction == GraphDirOut || q.Direction == GraphDirBoth
94 }
95
96 // IsInbound reports whether traversal follows inbound edges.
97 func (q *GraphQuery) IsInbound() bool {
98 return q.Direction == GraphDirIn || q.Direction == GraphDirBoth
99 }
100
101 // GraphResult is a depth-organized traversal result. Index 0 of each slice
102 // holds the nodes first discovered at depth 1.
103 //
104 // A node appears only at the depth where it was first seen. The response form
105 // keeps one entry per depth up to the deepest non-empty level, including empty
106 // slices for gaps.
107 type GraphResult struct {
108 PubkeysByDepth [][]string
109 EventsByDepth [][]string
110 TotalPubkeys int
111 TotalEvents int
112 Elapsed string
113
114 seenPub map[string]struct{}
115 seenEv map[string]struct{}
116 }
117
118 // NewGraphResult returns an empty result ready for Add calls.
119 func NewGraphResult() *GraphResult {
120 return &GraphResult{
121 seenPub: make(map[string]struct{}),
122 seenEv: make(map[string]struct{}),
123 }
124 }
125
126 // AddPubkeyAtDepth records a pubkey if it has not been seen before.
127 func (r *GraphResult) AddPubkeyAtDepth(pubkey string, depth int) bool {
128 if depth < 1 {
129 depth = 1
130 }
131 if r.seenPub == nil {
132 r.seenPub = make(map[string]struct{})
133 }
134 if _, ok := r.seenPub[pubkey]; ok {
135 return false
136 }
137 r.seenPub[pubkey] = struct{}{}
138 r.PubkeysByDepth = growDepth(r.PubkeysByDepth, depth)
139 r.PubkeysByDepth[depth-1] = append(r.PubkeysByDepth[depth-1], pubkey)
140 r.TotalPubkeys++
141 return true
142 }
143
144 // AddEventAtDepth records an event id if it has not been seen before.
145 func (r *GraphResult) AddEventAtDepth(id string, depth int) bool {
146 if depth < 1 {
147 depth = 1
148 }
149 if r.seenEv == nil {
150 r.seenEv = make(map[string]struct{})
151 }
152 if _, ok := r.seenEv[id]; ok {
153 return false
154 }
155 r.seenEv[id] = struct{}{}
156 r.EventsByDepth = growDepth(r.EventsByDepth, depth)
157 r.EventsByDepth[depth-1] = append(r.EventsByDepth[depth-1], id)
158 r.TotalEvents++
159 return true
160 }
161
162 func growDepth(dst [][]string, depth int) [][]string {
163 for len(dst) < depth {
164 dst = append(dst, nil)
165 }
166 return dst
167 }
168
169 // Sort orders every depth level lexicographically so relay responses are
170 // deterministic even though the underlying index scans depend on insertion
171 // order.
172 func (r *GraphResult) Sort() {
173 for _, level := range r.PubkeysByDepth {
174 sort.Strings(level)
175 }
176 for _, level := range r.EventsByDepth {
177 sort.Strings(level)
178 }
179 }
180
181 // AppendContentJSON appends the graph result's event content. Only the
182 // non-empty side of the result is emitted, matching orly's response shape.
183 func (r *GraphResult) AppendContentJSON(dst []byte) []byte {
184 dst = append(dst, '{')
185 first := true
186 field := func() {
187 if !first {
188 dst = append(dst, ',')
189 }
190 first = false
191 }
192 if len(r.PubkeysByDepth) > 0 {
193 field()
194 dst = append(dst, `"pubkeys_by_depth":`...)
195 dst = appendDepthArrays(dst, r.PubkeysByDepth)
196 dst = append(dst, `,"total_pubkeys":`...)
197 dst = strconv.AppendInt(dst, int64(r.TotalPubkeys), 10)
198 }
199 if len(r.EventsByDepth) > 0 {
200 field()
201 dst = append(dst, `"events_by_depth":`...)
202 dst = appendDepthArrays(dst, r.EventsByDepth)
203 dst = append(dst, `,"total_events":`...)
204 dst = strconv.AppendInt(dst, int64(r.TotalEvents), 10)
205 }
206 if r.Elapsed != "" {
207 field()
208 dst = append(dst, `"elapsed":`...)
209 dst = AppendJSONString(dst, r.Elapsed)
210 }
211 return append(dst, '}')
212 }
213
214 func appendDepthArrays(dst []byte, levels [][]string) []byte {
215 dst = append(dst, '[')
216 for i, level := range levels {
217 if i > 0 {
218 dst = append(dst, ',')
219 }
220 dst = append(dst, '[')
221 for j, id := range level {
222 if j > 0 {
223 dst = append(dst, ',')
224 }
225 dst = AppendJSONString(dst, id)
226 }
227 dst = append(dst, ']')
228 }
229 return append(dst, ']')
230 }
231