forked from cosmos/iavl
-
Notifications
You must be signed in to change notification settings - Fork 4
/
tree_fuzz_test.go
128 lines (109 loc) · 2.72 KB
/
tree_fuzz_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
// nolint:errcheck
package iavl
import (
"fmt"
"math/rand"
"testing"
"github.com/stretchr/testify/require"
cmn "github.com/cosmos/iavl/common"
)
// This file implement fuzz testing by generating programs and then running
// them. If an error occurs, the program that had the error is printed.
// A program is a list of instructions.
type program struct {
instructions []instruction
}
func (p *program) Execute(tree *MutableTree) (err error) {
var errLine int
defer func() {
if r := recover(); r != nil {
var str string
for i, instr := range p.instructions {
prefix := " "
if i == errLine {
prefix = ">> "
}
str += prefix + instr.String() + "\n"
}
err = fmt.Errorf("program panicked with: %s\n%s", r, str)
}
}()
for i, instr := range p.instructions {
errLine = i
instr.Execute(tree)
}
return
}
func (p *program) addInstruction(i instruction) {
p.instructions = append(p.instructions, i)
}
func (p *program) size() int {
return len(p.instructions)
}
type instruction struct {
op string
k, v []byte
version int64
}
func (i instruction) Execute(tree *MutableTree) {
switch i.op {
case "SET":
tree.Set(i.k, i.v)
case "REMOVE":
tree.Remove(i.k)
case "SAVE":
tree.SaveVersion()
case "DELETE":
tree.DeleteVersion(i.version)
default:
panic("Unrecognized op: " + i.op)
}
}
func (i instruction) String() string {
if i.version > 0 {
return fmt.Sprintf("%-8s %-8s %-8s %-8d", i.op, i.k, i.v, i.version)
}
return fmt.Sprintf("%-8s %-8s %-8s", i.op, i.k, i.v)
}
// Generate a random program of the given size.
func genRandomProgram(size int) *program {
p := &program{}
nextVersion := 1
for p.size() < size {
k, v := []byte(cmn.RandStr(1)), []byte(cmn.RandStr(1))
switch rand.Int() % 7 {
case 0, 1, 2:
p.addInstruction(instruction{op: "SET", k: k, v: v})
case 3, 4:
p.addInstruction(instruction{op: "REMOVE", k: k})
case 5:
p.addInstruction(instruction{op: "SAVE", version: int64(nextVersion)})
nextVersion++
case 6:
if rv := rand.Int() % nextVersion; rv < nextVersion && rv > 0 {
p.addInstruction(instruction{op: "DELETE", version: int64(rv)})
}
}
}
return p
}
// Generate many programs and run them.
func TestMutableTreeFuzz(t *testing.T) {
maxIterations := testFuzzIterations
progsPerIteration := 100000
iterations := 0
for size := 5; iterations < maxIterations; size++ {
for i := 0; i < progsPerIteration/size; i++ {
tree, err := getTestTree(0)
require.NoError(t, err)
program := genRandomProgram(size)
err = program.Execute(tree)
if err != nil {
str, err := tree.String()
require.Nil(t, err)
t.Fatalf("Error after %d iterations (size %d): %s\n%s", iterations, size, err.Error(), str)
}
iterations++
}
}
}