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
|
// Copyright 2023 syzkaller project authors. All rights reserved.
// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
package minimize
import (
"fmt"
"math"
"math/rand"
"testing"
"time"
"github.com/google/syzkaller/pkg/testutil"
"github.com/stretchr/testify/assert"
)
func TestBisectSliceToZero(t *testing.T) {
t.Parallel()
array := make([]int, 100)
ret, err := Slice(Config[int]{
Pred: func(arr []int) (bool, error) {
// No elements are needed.
return true, nil
},
Logf: t.Logf,
}, array)
assert.NoError(t, err)
assert.Len(t, ret, 0)
}
func TestBisectSliceFull(t *testing.T) {
t.Parallel()
array := make([]int, 100)
ret, err := Slice(Config[int]{
Pred: func(arr []int) (bool, error) {
// All elements are needed.
return false, nil
},
Logf: t.Logf,
}, array)
assert.NoError(t, err)
assert.Equal(t, ret, array)
}
func TestBisectRandomSlice(t *testing.T) {
t.Parallel()
r := rand.New(testutil.RandSource(t))
for i := 0; i < testutil.IterCount(); i++ {
// Create an array of random size and set the elements that must remain to non-zero values.
size := r.Intn(50)
subset := r.Intn(size + 1)
array := make([]int, size)
for _, j := range r.Perm(size)[:subset] {
array[j] = j + 1
}
var expect []int
for _, j := range array {
if j > 0 {
expect = append(expect, j)
}
}
predCalls := 0
ret, err := Slice(Config[int]{
Pred: func(arr []int) (bool, error) {
predCalls++
// All elements of the subarray must be present.
nonZero := 0
for _, x := range arr {
if x > 0 {
nonZero++
}
}
return nonZero == subset, nil
},
Logf: t.Logf,
}, array)
assert.NoError(t, err)
assert.EqualValues(t, expect, ret)
// Ensure we don't make too many predicate calls.
maxCalls := 3 + 2*subset*(1+int(math.Floor(math.Log2(float64(size)))))
assert.LessOrEqual(t, predCalls, maxCalls)
}
}
func BenchmarkSplits(b *testing.B) {
for _, guilty := range []int{1, 2, 3, 4} {
guilty := guilty
b.Run(fmt.Sprintf("%d_guilty", guilty), func(b *testing.B) {
var sum int
for i := 0; i < b.N; i++ {
sum += runMinimize(guilty)
}
b.ReportMetric(float64(sum)/float64(b.N), "remaining-elements")
})
}
}
func runMinimize(guilty int) int {
const size = 300
const steps = 5
r := rand.New(rand.NewSource(time.Now().UnixNano()))
array := make([]int, size)
for _, j := range r.Perm(size)[:guilty] {
array[j] = 1
}
ret, _ := Slice(Config[int]{
MaxSteps: steps,
Pred: func(arr []int) (bool, error) {
nonZero := 0
for _, x := range arr {
if x > 0 {
nonZero++
}
}
return nonZero == guilty, nil
},
}, array)
return len(ret)
}
|
