-
Notifications
You must be signed in to change notification settings - Fork 41
/
Copy pathexample_circularqueue_test.go
256 lines (228 loc) · 8.87 KB
/
example_circularqueue_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
package commands_test
import (
"fmt"
"github.com/leanovate/gopter"
"github.com/leanovate/gopter/commands"
"github.com/leanovate/gopter/gen"
)
// *****************************************
// Production code (i.e. the implementation)
// *****************************************
type Queue struct {
inp int
outp int
size int
buf []int
}
func New(n int) *Queue {
return &Queue{
inp: 0,
outp: 0,
size: n + 1,
buf: make([]int, n+1),
}
}
func (q *Queue) Put(n int) int {
if q.inp == 4 && n > 0 { // Intentional spooky bug
q.buf[q.size-1] *= n
}
q.buf[q.inp] = n
q.inp = (q.inp + 1) % q.size
return n
}
func (q *Queue) Get() int {
ans := q.buf[q.outp]
q.outp = (q.outp + 1) % q.size
return ans
}
func (q *Queue) Size() int {
return (q.inp - q.outp + q.size) % q.size
}
func (q *Queue) Init() {
q.inp = 0
q.outp = 0
}
// *****************************************
// Test code
// *****************************************
// cbState holds the expected state (i.e. its the commands.State)
type cbState struct {
size int
elements []int
takenElement int
}
func (st *cbState) TakeFront() {
st.takenElement = st.elements[0]
st.elements = append(st.elements[:0], st.elements[1:]...)
}
func (st *cbState) PushBack(value int) {
st.elements = append(st.elements, value)
}
func (st *cbState) String() string {
return fmt.Sprintf("State(size=%d, elements=%v)", st.size, st.elements)
}
// Get command simply invokes the Get function on the queue and compares the
// result with the expected state.
var genGetCommand = gen.Const(&commands.ProtoCommand{
Name: "Get",
RunFunc: func(q commands.SystemUnderTest) commands.Result {
return q.(*Queue).Get()
},
NextStateFunc: func(state commands.State) commands.State {
state.(*cbState).TakeFront()
return state
},
// The implementation implicitly assumes that Get is never called on an
// empty Queue, therefore the command requires a corresponding pre-condition
PreConditionFunc: func(state commands.State) bool {
return len(state.(*cbState).elements) > 0
},
PostConditionFunc: func(state commands.State, result commands.Result) *gopter.PropResult {
if result.(int) != state.(*cbState).takenElement {
return &gopter.PropResult{Status: gopter.PropFalse}
}
return &gopter.PropResult{Status: gopter.PropTrue}
},
})
// Put command puts a value into the queue by using the Put function. Since
// the Put function has an int argument the Put command should have a
// corresponding parameter.
type putCommand int
func (value putCommand) Run(q commands.SystemUnderTest) commands.Result {
return q.(*Queue).Put(int(value))
}
func (value putCommand) NextState(state commands.State) commands.State {
state.(*cbState).PushBack(int(value))
return state
}
// The implementation implicitly assumes that that Put is never called if
// the capacity is exhausted, therefore the command requires a corresponding
// pre-condition.
func (putCommand) PreCondition(state commands.State) bool {
s := state.(*cbState)
return len(s.elements) < s.size
}
func (putCommand) PostCondition(state commands.State, result commands.Result) *gopter.PropResult {
st := state.(*cbState)
if result.(int) != st.elements[len(st.elements)-1] {
return &gopter.PropResult{Status: gopter.PropFalse}
}
return &gopter.PropResult{Status: gopter.PropTrue}
}
func (value putCommand) String() string {
return fmt.Sprintf("Put(%d)", value)
}
// We want to have a generator for put commands for arbitrary int values.
// In this case the command is actually shrinkable, e.g. if the property fails
// by putting a 1000, it might already fail for a 500 as well ...
var genPutCommand = gen.Int().Map(func(value int) commands.Command {
return putCommand(value)
}).WithShrinker(func(v interface{}) gopter.Shrink {
return gen.IntShrinker(int(v.(putCommand))).Map(func(value int) putCommand {
return putCommand(value)
})
})
// Size command is simple again, it just invokes the Size function and
// compares compares the result with the expected state.
// The Size function can be called any time, therefore this command does not
// require a pre-condition.
var genSizeCommand = gen.Const(&commands.ProtoCommand{
Name: "Size",
RunFunc: func(q commands.SystemUnderTest) commands.Result {
return q.(*Queue).Size()
},
PostConditionFunc: func(state commands.State, result commands.Result) *gopter.PropResult {
if result.(int) != len(state.(*cbState).elements) {
return &gopter.PropResult{Status: gopter.PropFalse}
}
return &gopter.PropResult{Status: gopter.PropTrue}
},
})
// cbCommands implements the command.Commands interface, i.e. is
// responsible for creating/destroying the system under test and generating
// commands and initial states (cbState)
var cbCommands = &commands.ProtoCommands{
NewSystemUnderTestFunc: func(initialState commands.State) commands.SystemUnderTest {
s := initialState.(*cbState)
q := New(s.size)
for e := range s.elements {
q.Put(e)
}
return q
},
DestroySystemUnderTestFunc: func(sut commands.SystemUnderTest) {
sut.(*Queue).Init()
},
InitialStateGen: gen.IntRange(1, 30).Map(func(size int) *cbState {
return &cbState{
size: size,
elements: make([]int, 0, size),
}
}),
InitialPreConditionFunc: func(state commands.State) bool {
s := state.(*cbState)
return len(s.elements) >= 0 && len(s.elements) <= s.size
},
GenCommandFunc: func(state commands.State) gopter.Gen {
return gen.OneGenOf(genGetCommand, genPutCommand, genSizeCommand)
},
}
// Kudos to @jamesd for providing this real world example.
// ... of course he did not implemented the bug, that was evil me
//
// The bug only occures on the following conditions:
// - the queue size has to be greater than 4
// - the queue has to be filled entirely once
// - Get operations have to be at least 5 elements behind put
// - The Put at the end of the queue and 5 elements later have to be non-zero
//
// Lets see what gopter has to say:
//
// The output of this example will be
// ! circular buffer: Falsified after 96 passed tests.
// ARG_0: initialState=State(size=7, elements=[]) sequential=[Put(0) Put(0)
// Get Put(0) Get Put(0) Put(0) Get Put(0) Get Put(0) Get Put(-1) Put(0)
// Put(0) Put(0) Put(0) Get Get Put(2) Get]
// ARG_0_ORIGINAL (85 shrinks): initialState=State(size=7, elements=[])
// sequential=[Put(-1855365712) Put(-1591723498) Get Size Size
// Put(-1015561691) Get Put(397128011) Size Get Put(1943174048) Size
// Put(1309500770) Size Get Put(-879438231) Size Get Put(-1644094687) Get
// Put(-1818606323) Size Put(488620313) Size Put(-1219794505)
// Put(1166147059) Get Put(11390361) Get Size Put(-1407993944) Get Get Size
// Put(1393923085) Get Put(1222853245) Size Put(2070918543) Put(1741323168)
// Size Get Get Size Put(2019939681) Get Put(-170089451) Size Get Get Size
// Size Put(-49249034) Put(1229062846) Put(642598551) Get Put(1183453167)
// Size Get Get Get Put(1010460728) Put(6828709) Put(-185198587) Size Size
// Get Put(586459644) Get Size Put(-1802196502) Get Size Put(2097590857) Get
// Get Get Get Size Put(-474576011) Size Get Size Size Put(771190414) Size
// Put(-1509199920) Get Put(967212411) Size Get Put(578995532) Size Get Size
// Get]
//
// Though this is not the minimal possible combination of command, its already
// pretty close.
func Example_circularqueue() {
parameters := gopter.DefaultTestParametersWithSeed(1234) // Example should generate reproducible results, otherwise DefaultTestParameters() will suffice
properties := gopter.NewProperties(parameters)
properties.Property("circular buffer", commands.Prop(cbCommands))
// When using testing.T you might just use: properties.TestingRun(t)
properties.Run(gopter.ConsoleReporter(false))
// Output:
// ! circular buffer: Falsified after 96 passed tests.
// ARG_0: initialState=State(size=7, elements=[]) sequential=[Put(0) Put(0)
// Get Put(0) Get Put(0) Put(0) Get Put(0) Get Put(0) Get Put(-1) Put(0)
// Put(0) Put(0) Put(0) Get Get Put(2) Get]
// ARG_0_ORIGINAL (85 shrinks): initialState=State(size=7, elements=[])
// sequential=[Put(-1855365712) Put(-1591723498) Get Size Size
// Put(-1015561691) Get Put(397128011) Size Get Put(1943174048) Size
// Put(1309500770) Size Get Put(-879438231) Size Get Put(-1644094687) Get
// Put(-1818606323) Size Put(488620313) Size Put(-1219794505)
// Put(1166147059) Get Put(11390361) Get Size Put(-1407993944) Get Get Size
// Put(1393923085) Get Put(1222853245) Size Put(2070918543) Put(1741323168)
// Size Get Get Size Put(2019939681) Get Put(-170089451) Size Get Get Size
// Size Put(-49249034) Put(1229062846) Put(642598551) Get Put(1183453167)
// Size Get Get Get Put(1010460728) Put(6828709) Put(-185198587) Size Size
// Get Put(586459644) Get Size Put(-1802196502) Get Size Put(2097590857) Get
// Get Get Get Size Put(-474576011) Size Get Size Size Put(771190414) Size
// Put(-1509199920) Get Put(967212411) Size Get Put(578995532) Size Get Size
// Get]
}