1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // This package aids in the testing of code that uses channels.
16 // An Event is an element in a partially ordered set that either sends a value
17 // to a channel or expects a value from a channel.
25 type action
interface {
26 // getSend returns nil if the action is not a send action.
28 // getRecv returns nil if the action is not a receive action.
30 // getChannel returns the channel that the action operates on.
31 getChannel() interface{}
34 type recvAction
interface {
35 recvMatch(interface{}) bool
38 type sendAction
interface {
42 // isReady returns true if all the predecessors of an Event have occurred.
43 func (e Event
) isReady() bool {
44 for _
, predecessor
:= range e
.predecessors
{
45 if !predecessor
.occurred
{
53 // A Recv action reads a value from a channel and uses reflect.DeepMatch to
54 // compare it with an expected value.
60 func (r Recv
) getRecv() recvAction
{ return r
}
62 func (Recv
) getSend() sendAction
{ return nil }
64 func (r Recv
) getChannel() interface{} { return r
.Channel
}
66 func (r Recv
) recvMatch(chanEvent
interface{}) bool {
67 c
, ok
:= chanEvent
.(channelRecv
)
68 if !ok || c
.channel
!= r
.Channel
{
72 return reflect
.DeepEqual(c
.value
, r
.Expected
)
75 // A RecvMatch action reads a value from a channel and calls a function to
76 // determine if the value matches.
77 type RecvMatch
struct {
79 Match
func(interface{}) bool
82 func (r RecvMatch
) getRecv() recvAction
{ return r
}
84 func (RecvMatch
) getSend() sendAction
{ return nil }
86 func (r RecvMatch
) getChannel() interface{} { return r
.Channel
}
88 func (r RecvMatch
) recvMatch(chanEvent
interface{}) bool {
89 c
, ok
:= chanEvent
.(channelRecv
)
90 if !ok || c
.channel
!= r
.Channel
{
94 return r
.Match(c
.value
)
97 // A Closed action matches if the given channel is closed. The closing is
98 // treated as an event, not a state, thus Closed will only match once for a
104 func (r Closed
) getRecv() recvAction
{ return r
}
106 func (Closed
) getSend() sendAction
{ return nil }
108 func (r Closed
) getChannel() interface{} { return r
.Channel
}
110 func (r Closed
) recvMatch(chanEvent
interface{}) bool {
111 c
, ok
:= chanEvent
.(channelClosed
)
112 if !ok || c
.channel
!= r
.Channel
{
119 // A Send action sends a value to a channel. The value must match the
120 // type of the channel exactly unless the channel if of type chan interface{}.
126 func (Send
) getRecv() recvAction
{ return nil }
128 func (s Send
) getSend() sendAction
{ return s
}
130 func (s Send
) getChannel() interface{} { return s
.Channel
}
136 func newEmptyInterface(e empty
) reflect
.Value
{
137 return reflect
.NewValue(e
).(*reflect
.StructValue
).Field(0)
140 func (s Send
) send() {
141 // With reflect.ChanValue.Send, we must match the types exactly. So, if
142 // s.Channel is a chan interface{} we convert s.Value to an interface{}
144 c
:= reflect
.NewValue(s
.Channel
).(*reflect
.ChanValue
)
146 if iface
, ok
:= c
.Type().(*reflect
.ChanType
).Elem().(*reflect
.InterfaceType
); ok
&& iface
.NumMethod() == 0 {
147 v
= newEmptyInterface(empty
{s
.Value
})
149 v
= reflect
.NewValue(s
.Value
)
154 // A Close action closes the given channel.
159 func (Close
) getRecv() recvAction
{ return nil }
161 func (s Close
) getSend() sendAction
{ return s
}
163 func (s Close
) getChannel() interface{} { return s
.Channel
}
165 func (s Close
) send() { reflect
.NewValue(s
.Channel
).(*reflect
.ChanValue
).Close() }
167 // A ReceivedUnexpected error results if no active Events match a value
168 // received from a channel.
169 type ReceivedUnexpected
struct {
174 func (r ReceivedUnexpected
) String() string {
175 names
:= make([]string, len(r
.ready
))
176 for i
, v
:= range r
.ready
{
179 return fmt
.Sprintf("received unexpected value on one of the channels: %#v. Runnable events: %s", r
.Value
, strings
.Join(names
, ", "))
182 // A SetupError results if there is a error with the configuration of a set of
184 type SetupError
string
186 func (s SetupError
) String() string { return string(s
) }
188 func NewEvent(name
string, predecessors
[]*Event
, action action
) *Event
{
189 e
:= &Event
{name
, false, predecessors
, action
}
193 // Given a set of Events, Perform repeatedly iterates over the set and finds the
194 // subset of ready Events (that is, all of their predecessors have
195 // occurred). From that subset, it pseudo-randomly selects an Event to perform.
196 // If the Event is a send event, the send occurs and Perform recalculates the ready
197 // set. If the event is a receive event, Perform waits for a value from any of the
198 // channels that are contained in any of the events. That value is then matched
199 // against the ready events. The first event that matches is considered to
200 // have occurred and Perform recalculates the ready set.
202 // Perform continues this until all Events have occurred.
204 // Note that uncollected goroutines may still be reading from any of the
205 // channels read from after Perform returns.
207 // For example, consider the problem of testing a function that reads values on
208 // one channel and echos them to two output channels. To test this we would
209 // create three events: a send event and two receive events. Each of the
210 // receive events must list the send event as a predecessor but there is no
211 // ordering between the receive events.
213 // send := NewEvent("send", nil, Send{c, 1})
214 // recv1 := NewEvent("recv 1", []*Event{send}, Recv{c, 1})
215 // recv2 := NewEvent("recv 2", []*Event{send}, Recv{c, 1})
216 // Perform(0, []*Event{send, recv1, recv2})
218 // At first, only the send event would be in the ready set and thus Perform will
219 // send a value to the input channel. Now the two receive events are ready and
220 // Perform will match each of them against the values read from the output channels.
222 // It would be invalid to list one of the receive events as a predecessor of
223 // the other. At each receive step, all the receive channels are considered,
224 // thus Perform may see a value from a channel that is not in the current ready
226 func Perform(seed
int64, events
[]*Event
) (err os
.Error
) {
227 r
:= rand
.New(rand
.NewSource(seed
))
229 channels
, err
:= getChannels(events
)
233 multiplex
:= make(chan interface{})
234 for _
, channel
:= range channels
{
235 go recvValues(multiplex
, channel
)
240 ready
, err
:= readyEvents(events
)
246 // All events occurred.
250 event
:= ready
[r
.Intn(len(ready
))]
251 if send
:= event
.action
.getSend(); send
!= nil {
253 event
.occurred
= true
258 for _
, event
:= range ready
{
259 if recv
:= event
.action
.getRecv(); recv
!= nil && recv
.recvMatch(v
) {
260 event
.occurred
= true
265 return ReceivedUnexpected
{v
, ready
}
271 // getChannels returns all the channels listed in any receive events.
272 func getChannels(events
[]*Event
) ([]interface{}, os
.Error
) {
273 channels
:= make([]interface{}, len(events
))
276 for _
, event
:= range events
{
277 if recv
:= event
.action
.getRecv(); recv
== nil {
280 c
:= event
.action
.getChannel()
281 if _
, ok
:= reflect
.NewValue(c
).(*reflect
.ChanValue
); !ok
{
282 return nil, SetupError("one of the channel values is not a channel")
286 for _
, other
:= range channels
[0:j
] {
299 return channels
[0:j
], nil
302 // recvValues is a multiplexing helper function. It reads values from the given
303 // channel repeatedly, wrapping them up as either a channelRecv or
304 // channelClosed structure, and forwards them to the multiplex channel.
305 func recvValues(multiplex
chan<- interface{}, channel
interface{}) {
306 c
:= reflect
.NewValue(channel
).(*reflect
.ChanValue
)
311 multiplex
<- channelClosed
{channel
}
315 multiplex
<- channelRecv
{channel
, v
.Interface()}
319 type channelClosed
struct {
323 type channelRecv
struct {
328 // readyEvents returns the subset of events that are ready.
329 func readyEvents(events
[]*Event
) ([]*Event
, os
.Error
) {
330 ready
:= make([]*Event
, len(events
))
333 eventsWaiting
:= false
334 for _
, event
:= range events
{
346 if j
== 0 && eventsWaiting
{
347 names
:= make([]string, len(events
))
348 for _
, event
:= range events
{
352 names
[j
] = event
.name
355 return nil, SetupError("dependency cycle in events. These events are waiting to run but cannot: " + strings
.Join(names
, ", "))
358 return ready
[0:j
], nil