This repository has been archived by the owner on Jun 17, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 72
/
forkless_see_test.go
665 lines (611 loc) · 52.4 KB
/
forkless_see_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
package vector
import (
"fmt"
"math/rand"
"strconv"
"strings"
"testing"
"github.com/ethereum/go-ethereum/common"
"github.com/stretchr/testify/assert"
"github.com/Fantom-foundation/go-lachesis/src/hash"
"github.com/Fantom-foundation/go-lachesis/src/inter"
"github.com/Fantom-foundation/go-lachesis/src/inter/idx"
"github.com/Fantom-foundation/go-lachesis/src/inter/pos"
"github.com/Fantom-foundation/go-lachesis/src/kvdb/memorydb"
"github.com/Fantom-foundation/go-lachesis/src/logger"
)
func TestForklessSeenClassic(t *testing.T) {
t.Run("step 3", func(t *testing.T) {
testForklessSeen(t, `
a0_1(3) b0_1 c0_1
║ ║ ║
╠─────── b1_2 ║
║ ║ ║
║ ╠─────── c1_3
║ ║ ║
`)
})
t.Run("step 4", func(t *testing.T) {
testForklessSeen(t, `
a0_1(3) b0_1 c0_1
║ ║ ║
╠─────── b1_2 ║
║ ║ ║
║ ╠─────── c1_3
║ ║ ║
║ b2_4 ────╣
║ ║ ║
`)
})
t.Run("step 5", func(t *testing.T) {
testForklessSeen(t, `
a0_1(3) b0_1(5) c0_1(5)
║ ║ ║
╠─────── b1_2(5) ║
║ ║ ║
║ ╠─────── c1_3(5)
║ ║ ║
║ b2_4 ────╣
║ ║ ║
a1_5 ────╣ ║
║ ║ ║
`)
})
}
// testForklessSeen uses event name agreement:
// "<name>_<level>[(by-level)]",
// where by-level means that event is strongly seen by all event with level >= by-level.
func testForklessSeen(t *testing.T, dag string) {
logger.SetTestMode(t)
assertar := assert.New(t)
peers, _, _ := inter.ASCIIschemeToDAG(dag)
members := make(pos.Members, len(peers))
for _, peer := range peers {
members.Set(peer, pos.Stake(1))
}
vi := NewIndex(members, memorydb.New())
peers, _, named := inter.ASCIIschemeForEach(dag, inter.ForEachEvent{
Process: func(e *inter.Event, name string) {
vi.Add(e)
vi.Flush()
},
})
// check
for dsc, ev := range named {
_, bylevel := decode(dsc)
for dsc, by := range named {
level, _ := decode(dsc)
who := by.Hash()
whom := ev.Hash()
if !assertar.Equal(
bylevel > 0 && bylevel <= level,
vi.ForklessSee(who, whom),
fmt.Sprintf("%s strongly sees %s", who.String(), whom.String()),
) {
return
}
}
}
}
func decode(dsc string) (level, bylevel int64) {
var err error
s := strings.Split(dsc, "_")
s = strings.Split(s[1], "(")
level, err = strconv.ParseInt(s[0], 10, 32)
if err != nil {
panic(err)
}
if len(s) < 2 {
return
}
bylevel, err = strconv.ParseInt(strings.TrimRight(s[1], ")"), 10, 32)
if err != nil {
panic(err)
}
return
}
func TestForklessSeenRandom(t *testing.T) {
assertar := assert.New(t)
// generated by codegen4ForklessSeenStability()
dag := `
a000
║ ║
╠═══════ b000
║ ║ ║
║ ║ c000
║ ║ ║ ║
╠═══════─╫─══════─╫─══════ d000
║ ║ ║ ║
a001════─╫─══════─╫─═══════╣
║ ║ ║ ║
╠═══════ b001 ║ ║
║ ║ ║ ║
║ ╠═══════ c001 ║
║ ║ ║ ║
║ b002═════╣ ║
║ ║ ║ ║
║ ║ ╠═══════ d001
║ ║ ║ ║
a002════─╫─══════─╫─═══════╣
║ ║ ║ ║
a003═════╣ ║ ║
║ ║ ║ ║
╠═══════ b003 ║ ║
║ ║ ║ ║
║ ║ c002═════╣
║ ║║ ║ ║
║ ║╚══════─╫─══════ d002
║ ║ ║ ║
║ ║ c003═════╣
║ ║ ║ ║
║ ║ ╠═══════ d003
║ ║ ║ ║
a004════─╫─══════─╫─═══════╣
║ ║ ║ ║
╠═══════ b004 ║ ║
║ ║ ║ ║
║ ║ c004═════╣
║ ║ ║ ║
a005════─╫─═══════╣ ║
║ ║ ║ ║
╠═══════ b005 ║ ║
║ ║ ║ ║
║ ╠═══════ c005 ║
║ ║ ║ ║
a006════─╫─═══════╣ ║
║ ║ ║║ ║
║ ║ ║╚══════ d004
║ ║ ║ ║
║ ╠═══════─╫─══════ d005
║ ║ ║ ║
║ b006════─╫─═══════╣
║ ║ ║ ║
a007═════╣ ║ ║
║ ║ ║ ║
║ ║ c006═════╣
║ ║ ║ ║
║ ╠═══════─╫─══════ d006
║ ║ ║ ║
║ b007════─╫─═══════╣
║ ║ ║ ║
║ ║ c007═════╣
║ ║ ║ ║
╠═══════─╫─══════─╫─══════ d007
║ ║ ║ ║
a008════─╫─══════─╫─═══════╣
║ ║ ║ ║
║ b008════─╫─═══════╣
║ ║ ║ ║
║ ╠═══════ c008 ║
║ ║ ║ ║
a009════─╫─═══════╣ ║
║ ║ ║ ║
╠═══════ b009 ║ ║
║ ║ ║ ║
║ ║ ╠═══════ d008
║ ║ ║ ║
║ ║ c009═════╣
║ ║ ║ ║
║ b010═════╣ ║
║ ║ ║ ║
║ ║ ╠═══════ d009
║ ║ ║ ║
a010════─╫─══════─╫─═══════╣
║ ║ ║ ║
╠═══════─╫─══════ c010 ║
║ ║ ║ ║
║ b011═════╣ ║
║ ║ ║ ║
║ ╠═══════ c011 ║
║ ║║ ║ ║
║ ║╚══════─╫─══════ d010
║ ║ ║ ║
a011════─╫─══════─╫─═══════╣
║ ║ ║ ║
a012════─╫─═══════╣ ║
║ ║ ║ ║
╠═══════ b012 ║ ║
║ ║ ║ ║
╠═══════─╫─══════ c012 ║
║ ║ ║ ║
║ b013═════╣ ║
║ ║ ║ ║
║ ╠═══════ c013 ║
║ ║3 ║ ║
║ ║╚══════─╫─══════ d011
║ ║ ║║ ║
║ ║ ║╚══════ d012
║ ║ ║ ║
a013════─╫─══════─╫─═══════╣
║ ║ ║ ║
a014═════╣ ║ ║
║ ║ ║ ║
╠═══════─╫─══════ c014 ║
║ ║ ║║ ║
║ ║ ║╚══════ d013
║ ║ ║ ║
║ b014════─╫─═══════╣
║ ║ ║ ║
a015═════╣ ║ ║
║ ║ ║ ║
║ b015═════╣ ║
║ ║ ║ ║
║ ╠═══════ c015 ║
║ ║ ║ ║
a016════─╫─═══════╣ ║
║ ║ ║ ║
║ b016═════╣ ║
║ ║ ║ ║
╠═══════─╫─══════ c016 ║
║ ║ ║ ║
a017════─╫─═══════╣ ║
║ ║ ║ ║
║ b017═════╣ ║
║ ║ ║ ║
a018═════╣ ║ ║
║5 ║ ║ ║
║╚══════─╫─══════─╫─══════ d014
║ ║ ║║ ║
║ ║ ║╚══════ d015
║3 ║ ║ ║
║╚══════─╫─══════─╫─══════ d016
║ ║ ║ ║
║ ║ c017═════╣
║ ║ ║ ║
║ b018═════╣ ║
║ ║ ║ ║
║ ╠═══════ c018 ║
║ ║║ ║ ║
║ ║╚══════─╫─══════ d017
║ ║ ║ ║
║ ║ ╠═══════ d018
║ ║ ║ ║
a019════─╫─══════─╫─═══════╣
║ ║ ║ ║
║ b019════─╫─═══════╣
║ ║ ║ ║
╠═══════─╫─══════ c019 ║
║ ║ ║ ║
║ ║ ╠═══════ d019
`
relations := map[string]map[string]struct{}{
"a000": map[string]struct{}{},
"a001": map[string]struct{}{},
"a002": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "c000": {}, "c001": {}, "d000": {}},
"a003": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "c000": {}, "c001": {}, "d000": {}},
"a004": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "d000": {}, "d001": {}, "d002": {}},
"a005": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"a006": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"a007": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}},
"a008": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}},
"a009": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}},
"a010": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}},
"a011": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}},
"a012": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}},
"a013": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"a014": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"a015": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"a016": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"a017": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"a018": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"a019": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "b016": {}, "b017": {}, "b018": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "c017": {}, "c018": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}},
"b000": map[string]struct{}{},
"b001": map[string]struct{}{"a000": {}, "d000": {}},
"b002": map[string]struct{}{"a000": {}, "a001": {}, "d000": {}},
"b003": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "c000": {}, "c001": {}, "d000": {}, "d001": {}},
"b004": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"b005": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"b006": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"b007": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"b008": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}},
"b009": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}},
"b010": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}},
"b011": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}},
"b012": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"b013": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"b014": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"b015": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}},
"b016": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"b017": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"b018": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}},
"b019": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "b016": {}, "b017": {}, "b018": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "c017": {}, "c018": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}},
"c000": map[string]struct{}{},
"c001": map[string]struct{}{"a000": {}, "a001": {}, "d000": {}},
"c002": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "d000": {}},
"c003": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "d000": {}},
"c004": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "d000": {}},
"c005": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"c006": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"c007": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}},
"c008": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}},
"c009": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}},
"c010": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}},
"c011": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}},
"c012": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"c013": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"c014": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}},
"c015": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"c016": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"c017": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"c018": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}},
"c019": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "b016": {}, "b017": {}, "b018": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "c017": {}, "c018": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}, "d017": {}, "d018": {}},
"d000": map[string]struct{}{},
"d001": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "d000": {}},
"d002": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "c000": {}, "c001": {}, "d000": {}},
"d003": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "d000": {}},
"d004": map[string]struct{}{"a000": {}, "a001": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "d000": {}},
"d005": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"d006": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}},
"d007": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}},
"d008": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}},
"d009": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}},
"d010": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}},
"d011": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}},
"d012": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"d013": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"d014": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}},
"d015": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"d016": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"d017": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}},
"d018": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "b016": {}, "b017": {}, "b018": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "c017": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}},
"d019": map[string]struct{}{"a000": {}, "a001": {}, "a002": {}, "a003": {}, "a004": {}, "a005": {}, "a006": {}, "a007": {}, "a008": {}, "a009": {}, "a010": {}, "a011": {}, "a012": {}, "a013": {}, "a014": {}, "a015": {}, "a016": {}, "a017": {}, "a018": {}, "a019": {}, "b000": {}, "b001": {}, "b002": {}, "b003": {}, "b004": {}, "b005": {}, "b006": {}, "b007": {}, "b008": {}, "b009": {}, "b010": {}, "b011": {}, "b012": {}, "b013": {}, "b014": {}, "b015": {}, "b016": {}, "b017": {}, "b018": {}, "c000": {}, "c001": {}, "c002": {}, "c003": {}, "c004": {}, "c005": {}, "c006": {}, "c007": {}, "c008": {}, "c009": {}, "c010": {}, "c011": {}, "c012": {}, "c013": {}, "c014": {}, "c015": {}, "c016": {}, "c017": {}, "c018": {}, "d000": {}, "d001": {}, "d002": {}, "d003": {}, "d004": {}, "d005": {}, "d006": {}, "d007": {}, "d008": {}, "d009": {}, "d010": {}, "d011": {}, "d012": {}, "d013": {}, "d014": {}, "d015": {}, "d016": {}, "d017": {}, "d018": {}},
}
ordered := make([]*inter.Event, 0)
peers, _, named := inter.ASCIIschemeForEach(dag, inter.ForEachEvent{
Process: func(e *inter.Event, name string) {
ordered = append(ordered, e)
},
})
members := make(pos.Members, len(peers))
for _, peer := range peers {
members.Set(peer, pos.Stake(1))
}
vi := NewIndex(members, memorydb.New())
// push
for _, e := range ordered {
vi.Add(e)
vi.Flush()
}
// check
for e1name, e1 := range named {
for e2name, e2 := range named {
_, expect := relations[e1name][e2name]
if !assertar.Equal(
expect,
vi.ForklessSee(e1.Hash(), e2.Hash()),
fmt.Sprintf("%s strongly sees %s", e1.Hash(), e2.Hash()),
) {
return
}
}
}
}
type eventSlot struct {
seq idx.Event
creator common.Address
}
// naive implementation of fork detection, O(n)
func test_forksSeen(vi *Index, head hash.Event) (cheaters map[common.Address]bool, err error) {
cheaters = map[common.Address]bool{}
visited := hash.EventsSet{}
seen := map[eventSlot]int{}
err = vi.dfsSubgraph(head, func(e *event) (godeeper bool) {
// ensure visited once
if visited.Contains(e.Hash()) {
return false
}
visited.Add(e.Hash())
slot := eventSlot{
seq: e.Seq,
creator: e.Creator,
}
seen[slot] += 1
return true
})
for s, count := range seen {
if count > 1 {
cheaters[s.creator] = true
}
}
return cheaters, err
}
func TestRandomForksSanity(t *testing.T) {
nodes := inter.GenNodes(8)
cheaters := []common.Address{nodes[0], nodes[1], nodes[2]}
members := make(pos.Members, len(nodes))
for _, peer := range nodes {
members.Set(peer, pos.Stake(1))
}
members.Set(cheaters[0], pos.Stake(2))
members.Set(nodes[3], pos.Stake(2))
members.Set(nodes[4], pos.Stake(3))
vi := NewIndex(members, memorydb.New())
processed := make(map[hash.Event]*inter.Event)
// Many forks from each node in large graph, so probability of not seeing a fork is negligible
events := inter.ForEachRandFork(nodes, cheaters, 300, 4, 30, nil, inter.ForEachEvent{
Process: func(e *inter.Event, name string) {
if _, ok := processed[e.Hash()]; ok {
return
}
processed[e.Hash()] = e
vi.Add(e)
},
})
vi.Flush()
vi.DropNotFlushed() // don't drop anything, because everything is flushed
// quick sanity check. all the nodes should see that cheaters have a fork, and honest nodes don't have forks
assertar := assert.New(t)
idxs := members.Idxs()
for _, node := range nodes {
ee := events[node]
highestBefore := vi.GetEvent(ee[len(ee)-1].Hash()).HighestBefore
for n, cheater := range nodes {
high := highestBefore[idxs[cheater]]
isCheater := n < len(cheaters)
assertar.Equal(isCheater, high.IsForkSeen, cheater.String())
if isCheater {
assertar.Equal(idx.Event(0), high.Seq, cheater.String())
} else {
assertar.NotEqual(idx.Event(0), high.Seq, cheater.String())
}
}
}
}
func TestRandomForks(t *testing.T) {
for i, test := range []struct {
nodesNum int
cheatersNum int
eventsNum int
forksNum int
parentsNum int
}{
{
nodesNum: 1,
parentsNum: 1,
cheatersNum: 1,
eventsNum: 10,
forksNum: 3,
},
{
nodesNum: 2,
parentsNum: 1,
cheatersNum: 1,
eventsNum: 10,
forksNum: 3,
},
{
nodesNum: 2,
parentsNum: 2,
cheatersNum: 2,
eventsNum: 10,
forksNum: 3,
},
{
nodesNum: 10,
parentsNum: 4,
cheatersNum: 1,
eventsNum: 10,
forksNum: 3,
},
{
nodesNum: 10,
parentsNum: 4,
cheatersNum: 10,
eventsNum: 10,
forksNum: 3,
},
{
nodesNum: 20,
parentsNum: 4,
cheatersNum: 10,
eventsNum: 5,
forksNum: 2,
},
{
nodesNum: 40,
parentsNum: 4,
cheatersNum: 10,
eventsNum: 3,
forksNum: 1,
},
{
nodesNum: 5,
parentsNum: 4,
cheatersNum: 2,
eventsNum: 30,
forksNum: 30,
},
} {
t.Run(fmt.Sprintf("Test #%d", i), func(t *testing.T) {
r := rand.New(rand.NewSource(int64(i)))
nodes := inter.GenNodes(test.nodesNum)
cheaters := nodes[:test.cheatersNum]
members := make(pos.Members, len(nodes))
for _, peer := range nodes {
members.Set(peer, pos.Stake(1))
}
vi := NewIndex(members, memorydb.New())
processed := make(map[hash.Event]*inter.Event)
_ = inter.ForEachRandFork(nodes, cheaters, test.eventsNum, test.parentsNum, test.forksNum, r, inter.ForEachEvent{
Process: func(e *inter.Event, name string) {
if _, ok := processed[e.Hash()]; ok {
return
}
processed[e.Hash()] = e
vi.Add(e)
},
})
assertar := assert.New(t)
idxs := members.Idxs()
// check that fork seeing is identical to naive version
for _, e := range processed {
highestBefore := vi.GetEvent(e.Hash()).HighestBefore
expectedCheaters, err := test_forksSeen(vi, e.Hash())
assertar.NoError(err)
for _, cheater := range nodes {
expectedCheater := expectedCheaters[cheater]
high := highestBefore[idxs[cheater]]
assertar.Equal(expectedCheater, high.IsForkSeen, cheater.String()+"_"+e.Creator.String())
if expectedCheater {
assertar.Equal(idx.Event(0), high.Seq, cheater.String()+"_"+e.Creator.String())
}
}
}
vi.DropNotFlushed() // drops everything
for _, e := range processed {
assertar.Nil(vi.GetEvent(e.Hash()))
}
})
}
}
/*
// codegen4ForklessSeenStability is for test data generation.
func codegen4ForklessSeenStability() {
peers := inter.GenNodes(4)
events := inter.GenEventsByNode(peers, 20, 2, nil, nil, nil)
members := make(pos.Members, len(peers))
for _, peer := range peers {
members.Set(peer, pos.Stake(1))
}
vi := NewIndex(members, memorydb.New())
processed := make(map[hash.Event]*inter.Event)
orderThenProcess := ordering.EventBuffer(ordering.Callback{
Process: func(e *inter.Event) {
processed[e.Hash()] = e
vi.Add(e)
},
Drop: func(e *inter.Event, err error) {
panic(err)
},
Exists: func(h hash.Event) *inter.Event {
return processed[h]
},
})
// push
dag := inter.Events{}
for _, ee := range events {
for _, e := range ee {
orderThenProcess(e)
}
dag = append(dag, ee...)
}
// generation
scheme, err := inter.DAGtoASCIIscheme(dag)
if err != nil {
panic(err)
}
fmt.Printf("dag := `%s`\n", scheme)
fmt.Printf("relations := map[string]map[string]struct{}{\n")
for _, e1 := range dag {
sees := fmt.Sprintf("\"%s\": map[string]struct{}{", e1.Hash())
for _, e2 := range dag {
if vi.ForklessSee(e1.Hash(), e2.Hash()) {
sees = sees + fmt.Sprintf("\"%s\":{},", e2.Hash())
}
}
sees += "},"
fmt.Println(sees)
}
fmt.Printf("}\n")
}
*/