oppi.li
1// This file contains tests which are the same across language implementations.
2// AKA, if you update this file, you should probably update the corresponding
3// file in atproto repo (typescript)
4package mst
5
6import (
7 "context"
8 "fmt"
9 "testing"
10
11 "github.com/bluesky-social/indigo/util"
12 "github.com/stretchr/testify/assert"
13
14 "github.com/ipfs/go-cid"
15)
16
17func TestLeadingZeros(t *testing.T) {
18 msg := "MST 'depth' computation (SHA-256 leading zeros)"
19 assert.Equal(t, leadingZerosOnHash(""), 0, msg)
20 assert.Equal(t, leadingZerosOnHash("asdf"), 0, msg)
21 assert.Equal(t, leadingZerosOnHash("blue"), 1, msg)
22 assert.Equal(t, leadingZerosOnHash("2653ae71"), 0, msg)
23 assert.Equal(t, leadingZerosOnHash("88bfafc7"), 2, msg)
24 assert.Equal(t, leadingZerosOnHash("2a92d355"), 4, msg)
25 assert.Equal(t, leadingZerosOnHash("884976f5"), 6, msg)
26 assert.Equal(t, leadingZerosOnHash("app.bsky.feed.post/454397e440ec"), 4, msg)
27 assert.Equal(t, leadingZerosOnHash("app.bsky.feed.post/9adeb165882c"), 8, msg)
28}
29
30func TestPrefixLen(t *testing.T) {
31 msg := "length of common prefix between strings"
32 assert.Equal(t, countPrefixLen("abc", "abc"), 3, msg)
33 assert.Equal(t, countPrefixLen("", "abc"), 0, msg)
34 assert.Equal(t, countPrefixLen("abc", ""), 0, msg)
35 assert.Equal(t, countPrefixLen("ab", "abc"), 2, msg)
36 assert.Equal(t, countPrefixLen("abc", "ab"), 2, msg)
37 assert.Equal(t, countPrefixLen("abcde", "abc"), 3, msg)
38 assert.Equal(t, countPrefixLen("abc", "abcde"), 3, msg)
39 assert.Equal(t, countPrefixLen("abcde", "abc1"), 3, msg)
40 assert.Equal(t, countPrefixLen("abcde", "abb"), 2, msg)
41 assert.Equal(t, countPrefixLen("abcde", "qbb"), 0, msg)
42 assert.Equal(t, countPrefixLen("abc", "abc\x00"), 3, msg)
43 assert.Equal(t, countPrefixLen("abc\x00", "abc"), 3, msg)
44}
45
46func TestPrefixLenWide(t *testing.T) {
47 // NOTE: these are not cross-language consistent!
48 msg := "length of common prefix between strings (wide chars)"
49 assert.Equal(t, len("jalapeño"), 9, msg) // 8 in javascript
50 assert.Equal(t, len("💩"), 4, msg) // 2 in javascript
51 assert.Equal(t, len("👩👧👧"), 18, msg) // 8 in javascript
52
53 // many of the below are different in JS
54 assert.Equal(t, countPrefixLen("jalapeño", "jalapeno"), 6, msg)
55 assert.Equal(t, countPrefixLen("jalapeñoA", "jalapeñoB"), 9, msg)
56 assert.Equal(t, countPrefixLen("coöperative", "coüperative"), 3, msg)
57 assert.Equal(t, countPrefixLen("abc💩abc", "abcabc"), 3, msg)
58 assert.Equal(t, countPrefixLen("💩abc", "💩ab"), 6, msg)
59 assert.Equal(t, countPrefixLen("abc👩👦👦de", "abc👩👧👧de"), 13, msg)
60}
61
62func mapToCidMapDecode(t *testing.T, a map[string]string) map[string]cid.Cid {
63 out := make(map[string]cid.Cid)
64 for k, v := range a {
65 c, err := cid.Decode(v)
66 if err != nil {
67 t.Fatal(err)
68 }
69 out[k] = c
70 }
71 return out
72}
73
74func mapToMstRootCidString(t *testing.T, m map[string]string) string {
75 bs := memBs()
76 ctx := context.Background()
77 mst := cidMapToMst(t, bs, mapToCidMapDecode(t, m))
78 ncid, err := mst.GetPointer(ctx)
79 if err != nil {
80 t.Fatal(err)
81 }
82 return ncid.String()
83}
84
85func TestAllowedKeys(t *testing.T) {
86
87 bs := memBs()
88 ctx := context.Background()
89 cid1str := "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
90 cid1, err := cid.Decode(cid1str)
91 if err != nil {
92 t.Fatal(err)
93 }
94
95 empty := map[string]string{}
96 mst := cidMapToMst(t, bs, mapToCidMapDecode(t, empty))
97
98 // rejects empty key
99 _, err = mst.Add(ctx, "", cid1, -1)
100 assert.NotNil(t, err)
101
102 // rejects a key with no collection
103 _, err = mst.Add(ctx, "asdf", cid1, -1)
104 assert.NotNil(t, err)
105
106 // rejects a key with a nested collection
107 _, err = mst.Add(ctx, "nested/collection/asdf", cid1, -1)
108 assert.NotNil(t, err)
109
110 // rejects on empty coll or rkey
111 _, err = mst.Add(ctx, "coll/", cid1, -1)
112 assert.NotNil(t, err)
113 _, err = mst.Add(ctx, "/rkey", cid1, -1)
114 assert.NotNil(t, err)
115
116 // rejects non-ascii chars
117 _, err = mst.Add(ctx, "coll/jalapeñoA", cid1, -1)
118 assert.NotNil(t, err)
119 _, err = mst.Add(ctx, "coll/coöperative", cid1, -1)
120 assert.NotNil(t, err)
121 _, err = mst.Add(ctx, "coll/abc💩", cid1, -1)
122 assert.NotNil(t, err)
123
124 // rejects ascii that we dont support
125 _, err = mst.Add(ctx, "coll/key$", cid1, -1)
126 assert.NotNil(t, err)
127 _, err = mst.Add(ctx, "coll/key%", cid1, -1)
128 assert.NotNil(t, err)
129 _, err = mst.Add(ctx, "coll/key(", cid1, -1)
130 assert.NotNil(t, err)
131 _, err = mst.Add(ctx, "coll/key)", cid1, -1)
132 assert.NotNil(t, err)
133 _, err = mst.Add(ctx, "coll/key+", cid1, -1)
134 assert.NotNil(t, err)
135 _, err = mst.Add(ctx, "coll/key=", cid1, -1)
136 assert.NotNil(t, err)
137
138 // rejects keys over 256 chars
139 _, err = mst.Add(ctx, "coll/asdofiupoiwqeurfpaosidfuapsodirupasoirupasoeiruaspeoriuaspeoriu2p3o4iu1pqw3oiuaspdfoiuaspdfoiuasdfpoiasdufpwoieruapsdofiuaspdfoiuasdpfoiausdfpoasidfupasodifuaspdofiuasdpfoiasudfpoasidfuapsodfiuasdpfoiausdfpoasidufpasodifuapsdofiuasdpofiuasdfpoaisdufpao", cid1, -1)
140 assert.NotNil(t, err)
141
142 // allows long key under 256 chars
143 _, err = mst.Add(ctx, "coll/asdofiupoiwqeurfpaosidfuapsodirupasoirupasoeiruaspeoriuaspeoriu2p3o4iu1pqw3oiuaspdfoiuaspdfoiuasdfpoiasdufpwoieruapsdofiuaspdfoiuasdpfoiausdfpoasidfupasodifuaspdofiuasdpfoiasudfpoasidfuapsodfiuasdpfoiausdfpoasidufpasodifuapsdofiuasdpofiuasdfpoaisduf", cid1, -1)
144 assert.Nil(t, err)
145
146 // allows URL-safe chars
147 _, err = mst.Add(ctx, "coll/key0", cid1, -1)
148 assert.Nil(t, err)
149 _, err = mst.Add(ctx, "coll/key_", cid1, -1)
150 assert.Nil(t, err)
151 _, err = mst.Add(ctx, "coll/key:", cid1, -1)
152 assert.Nil(t, err)
153 _, err = mst.Add(ctx, "coll/key.", cid1, -1)
154 assert.Nil(t, err)
155 _, err = mst.Add(ctx, "coll/key-", cid1, -1)
156 assert.Nil(t, err)
157
158}
159
160func TestManualNode(t *testing.T) {
161
162 bs := memBs()
163 cst := util.CborStore(bs)
164 cid1, err := cid.Decode("bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454")
165 if err != nil {
166 t.Fatal(err)
167 }
168
169 simple_nd := NodeData{
170 Left: nil,
171 Entries: []TreeEntry{
172 {
173 PrefixLen: 0,
174 KeySuffix: []byte("com.example.record/3jqfcqzm3fo2j"),
175 Val: cid1,
176 Tree: nil,
177 },
178 },
179 }
180 mcid, err := cst.Put(context.TODO(), &simple_nd)
181 if err != nil {
182 t.Fatal(err)
183 }
184 block, err := bs.Get(context.TODO(), mcid)
185 if err != nil {
186 t.Fatal(err)
187 }
188 if false {
189 fmt.Printf("%#v\n", block)
190 }
191 assert.Equal(t, mcid.String(), "bafyreibj4lsc3aqnrvphp5xmrnfoorvru4wynt6lwidqbm2623a6tatzdu")
192
193}
194
195func TestInteropKnownMaps(t *testing.T) {
196
197 cid1str := "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
198
199 // empty map
200 emptyMap := map[string]string{}
201 assert.Equal(t, mapToMstRootCidString(t, emptyMap), "bafyreie5737gdxlw5i64vzichcalba3z2v5n6icifvx5xytvske7mr3hpm")
202
203 // no depth, single entry
204 trivialMap := map[string]string{
205 "com.example.record/3jqfcqzm3fo2j": cid1str,
206 }
207 assert.Equal(t, mapToMstRootCidString(t, trivialMap), "bafyreibj4lsc3aqnrvphp5xmrnfoorvru4wynt6lwidqbm2623a6tatzdu")
208
209 // single layer=2 entry
210 singlelayer2Map := map[string]string{
211 "com.example.record/3jqfcqzm3fx2j": cid1str,
212 }
213 assert.Equal(t, mapToMstRootCidString(t, singlelayer2Map), "bafyreih7wfei65pxzhauoibu3ls7jgmkju4bspy4t2ha2qdjnzqvoy33ai")
214
215 // pretty simple, but with some depth
216 simpleMap := map[string]string{
217 "com.example.record/3jqfcqzm3fp2j": cid1str,
218 "com.example.record/3jqfcqzm3fr2j": cid1str,
219 "com.example.record/3jqfcqzm3fs2j": cid1str,
220 "com.example.record/3jqfcqzm3ft2j": cid1str,
221 "com.example.record/3jqfcqzm4fc2j": cid1str,
222 }
223 assert.Equal(t, mapToMstRootCidString(t, simpleMap), "bafyreicmahysq4n6wfuxo522m6dpiy7z7qzym3dzs756t5n7nfdgccwq7m")
224}
225
226func TestInteropKnownMapsTricky(t *testing.T) {
227 t.Skip("TODO: these are currently disallowed in typescript implementation")
228
229 cid1str := "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
230
231 // include several known edge cases
232 trickyMap := map[string]string{
233 "": cid1str,
234 "jalapeño": cid1str,
235 "coöperative": cid1str,
236 "coüperative": cid1str,
237 "abc\x00": cid1str,
238 }
239 assert.Equal(t, mapToMstRootCidString(t, trickyMap), "bafyreiecb33zh7r2sc3k2wthm6exwzfktof63kmajeildktqc25xj6qzx4")
240}
241
242// "trims top of tree on delete"
243func TestInteropEdgeCasesTrimTop(t *testing.T) {
244
245 bs := memBs()
246 ctx := context.Background()
247 cid1str := "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
248 l1root := "bafyreifnqrwbk6ffmyaz5qtujqrzf5qmxf7cbxvgzktl4e3gabuxbtatv4"
249 l0root := "bafyreie4kjuxbwkhzg2i5dljaswcroeih4dgiqq6pazcmunwt2byd725vi"
250
251 trimMap := map[string]string{
252 "com.example.record/3jqfcqzm3fn2j": cid1str, // level 0
253 "com.example.record/3jqfcqzm3fo2j": cid1str, // level 0
254 "com.example.record/3jqfcqzm3fp2j": cid1str, // level 0
255 "com.example.record/3jqfcqzm3fs2j": cid1str, // level 0
256 "com.example.record/3jqfcqzm3ft2j": cid1str, // level 0
257 "com.example.record/3jqfcqzm3fu2j": cid1str, // level 1
258 }
259 trimMst := cidMapToMst(t, bs, mapToCidMapDecode(t, trimMap))
260 trimBefore, err := trimMst.GetPointer(ctx)
261 if err != nil {
262 t.Fatal(err)
263 }
264 assert.Equal(t, trimMst.layer, 1)
265 assert.Equal(t, trimBefore.String(), l1root)
266
267 trimMst, err = trimMst.Delete(ctx, "com.example.record/3jqfcqzm3fs2j") // level 1
268 if err != nil {
269 t.Fatal(err)
270 }
271 trimAfter, err := trimMst.GetPointer(ctx)
272 if err != nil {
273 t.Fatal(err)
274 }
275 fmt.Printf("%#v\n", trimMst)
276 assert.Equal(t, trimMst.layer, 0)
277 assert.Equal(t, trimAfter.String(), l0root)
278}
279
280func TestInteropEdgeCasesInsertion(t *testing.T) {
281
282 bs := memBs()
283 ctx := context.Background()
284 cid1str := "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
285 cid1, err := cid.Decode(cid1str)
286 if err != nil {
287 t.Fatal(err)
288 }
289
290 // "handles insertion that splits two layers down"
291 l1root := "bafyreiettyludka6fpgp33stwxfuwhkzlur6chs4d2v4nkmq2j3ogpdjem"
292 l2root := "bafyreid2x5eqs4w4qxvc5jiwda4cien3gw2q6cshofxwnvv7iucrmfohpm"
293 insertionMap := map[string]string{
294 "com.example.record/3jqfcqzm3fo2j": cid1str, // A; level 0
295 "com.example.record/3jqfcqzm3fp2j": cid1str, // B; level 0
296 "com.example.record/3jqfcqzm3fr2j": cid1str, // C; level 0
297 "com.example.record/3jqfcqzm3fs2j": cid1str, // D; level 1
298 "com.example.record/3jqfcqzm3ft2j": cid1str, // E; level 0
299 "com.example.record/3jqfcqzm3fz2j": cid1str, // G; level 0
300 "com.example.record/3jqfcqzm4fc2j": cid1str, // H; level 0
301 "com.example.record/3jqfcqzm4fd2j": cid1str, // I; level 1
302 "com.example.record/3jqfcqzm4ff2j": cid1str, // J; level 0
303 "com.example.record/3jqfcqzm4fg2j": cid1str, // K; level 0
304 "com.example.record/3jqfcqzm4fh2j": cid1str, // L; level 0
305 }
306 insertionMst := cidMapToMst(t, bs, mapToCidMapDecode(t, insertionMap))
307 insertionBefore, err := insertionMst.GetPointer(ctx)
308 if err != nil {
309 t.Fatal(err)
310 }
311 assert.Equal(t, insertionMst.layer, 1)
312 assert.Equal(t, insertionBefore.String(), l1root)
313
314 // insert F, which will push E out of the node with G+H to a new node under D
315 insertionMst, err = insertionMst.Add(ctx, "com.example.record/3jqfcqzm3fx2j", cid1, -1) // F; level 2
316 if err != nil {
317 t.Fatal(err)
318 }
319 insertionAfter, err := insertionMst.GetPointer(ctx)
320 if err != nil {
321 t.Fatal(err)
322 }
323 assert.Equal(t, insertionMst.layer, 2)
324 assert.Equal(t, insertionAfter.String(), l2root)
325
326 // remove F, which should push E back over with G+H
327 insertionMst, err = insertionMst.Delete(ctx, "com.example.record/3jqfcqzm3fx2j") // F; level 2
328 if err != nil {
329 t.Fatal(err)
330 }
331 insertionFinal, err := insertionMst.GetPointer(ctx)
332 if err != nil {
333 t.Fatal(err)
334 }
335 assert.Equal(t, insertionMst.layer, 1)
336 assert.Equal(t, insertionFinal.String(), l1root)
337}
338
339// "handles new layers that are two higher than existing"
340func TestInteropEdgeCasesHigher(t *testing.T) {
341
342 bs := memBs()
343 ctx := context.Background()
344 cid1str := "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
345 cid1, err := cid.Decode(cid1str)
346 if err != nil {
347 t.Fatal(err)
348 }
349
350 l0root := "bafyreidfcktqnfmykz2ps3dbul35pepleq7kvv526g47xahuz3rqtptmky"
351 l2root := "bafyreiavxaxdz7o7rbvr3zg2liox2yww46t7g6hkehx4i4h3lwudly7dhy"
352 l2root2 := "bafyreig4jv3vuajbsybhyvb7gggvpwh2zszwfyttjrj6qwvcsp24h6popu"
353 higherMap := map[string]string{
354 "com.example.record/3jqfcqzm3ft2j": cid1str, // A; level 0
355 "com.example.record/3jqfcqzm3fz2j": cid1str, // C; level 0
356 }
357 higherMst := cidMapToMst(t, bs, mapToCidMapDecode(t, higherMap))
358 higherBefore, err := higherMst.GetPointer(ctx)
359 if err != nil {
360 t.Fatal(err)
361 }
362 assert.Equal(t, higherMst.layer, 0)
363 assert.Equal(t, higherBefore.String(), l0root)
364
365 // insert B, which is two levels above
366 higherMst, err = higherMst.Add(ctx, "com.example.record/3jqfcqzm3fx2j", cid1, -1) // B; level 2
367 if err != nil {
368 t.Fatal(err)
369 }
370 higherAfter, err := higherMst.GetPointer(ctx)
371 if err != nil {
372 t.Fatal(err)
373 }
374 assert.Equal(t, higherAfter.String(), l2root)
375
376 // remove B
377 higherMst, err = higherMst.Delete(ctx, "com.example.record/3jqfcqzm3fx2j") // B; level 2
378 if err != nil {
379 t.Fatal(err)
380 }
381 higherAgain, err := higherMst.GetPointer(ctx)
382 if err != nil {
383 t.Fatal(err)
384 }
385 assert.Equal(t, higherMst.layer, 0)
386 assert.Equal(t, higherAgain.String(), l0root)
387
388 // insert B (level=2) and D (level=1)
389 higherMst, err = higherMst.Add(ctx, "com.example.record/3jqfcqzm3fx2j", cid1, -1) // B; level 2
390 if err != nil {
391 t.Fatal(err)
392 }
393 higherMst, err = higherMst.Add(ctx, "com.example.record/3jqfcqzm4fd2j", cid1, -1) // D; level 1
394 if err != nil {
395 t.Fatal(err)
396 }
397 higherYetAgain, err := higherMst.GetPointer(ctx)
398 if err != nil {
399 t.Fatal(err)
400 }
401 assert.Equal(t, higherMst.layer, 2)
402 assert.Equal(t, higherYetAgain.String(), l2root2)
403
404 // remove D
405 higherMst, err = higherMst.Delete(ctx, "com.example.record/3jqfcqzm4fd2j") // D; level 1
406 if err != nil {
407 t.Fatal(err)
408 }
409 higherFinal, err := higherMst.GetPointer(ctx)
410 if err != nil {
411 t.Fatal(err)
412 }
413 assert.Equal(t, higherMst.layer, 2)
414 assert.Equal(t, higherFinal.String(), l2root)
415}