blob: afb286f5b866519a2789fdb6900fcccd3bd741d7 [file] [log] [blame]
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package script aids in the testing of code that uses channels.
package script
import (
"fmt"
"os"
"rand"
"reflect"
"strings"
)
// An Event is an element in a partially ordered set that either sends a value
// to a channel or expects a value from a channel.
type Event struct {
name string
occurred bool
predecessors []*Event
action action
}
type action interface {
// getSend returns nil if the action is not a send action.
getSend() sendAction
// getRecv returns nil if the action is not a receive action.
getRecv() recvAction
// getChannel returns the channel that the action operates on.
getChannel() interface{}
}
type recvAction interface {
recvMatch(interface{}) bool
}
type sendAction interface {
send()
}
// isReady returns true if all the predecessors of an Event have occurred.
func (e Event) isReady() bool {
for _, predecessor := range e.predecessors {
if !predecessor.occurred {
return false
}
}
return true
}
// A Recv action reads a value from a channel and uses reflect.DeepMatch to
// compare it with an expected value.
type Recv struct {
Channel interface{}
Expected interface{}
}
func (r Recv) getRecv() recvAction { return r }
func (Recv) getSend() sendAction { return nil }
func (r Recv) getChannel() interface{} { return r.Channel }
func (r Recv) recvMatch(chanEvent interface{}) bool {
c, ok := chanEvent.(channelRecv)
if !ok || c.channel != r.Channel {
return false
}
return reflect.DeepEqual(c.value, r.Expected)
}
// A RecvMatch action reads a value from a channel and calls a function to
// determine if the value matches.
type RecvMatch struct {
Channel interface{}
Match func(interface{}) bool
}
func (r RecvMatch) getRecv() recvAction { return r }
func (RecvMatch) getSend() sendAction { return nil }
func (r RecvMatch) getChannel() interface{} { return r.Channel }
func (r RecvMatch) recvMatch(chanEvent interface{}) bool {
c, ok := chanEvent.(channelRecv)
if !ok || c.channel != r.Channel {
return false
}
return r.Match(c.value)
}
// A Closed action matches if the given channel is closed. The closing is
// treated as an event, not a state, thus Closed will only match once for a
// given channel.
type Closed struct {
Channel interface{}
}
func (r Closed) getRecv() recvAction { return r }
func (Closed) getSend() sendAction { return nil }
func (r Closed) getChannel() interface{} { return r.Channel }
func (r Closed) recvMatch(chanEvent interface{}) bool {
c, ok := chanEvent.(channelClosed)
if !ok || c.channel != r.Channel {
return false
}
return true
}
// A Send action sends a value to a channel. The value must match the
// type of the channel exactly unless the channel if of type chan interface{}.
type Send struct {
Channel interface{}
Value interface{}
}
func (Send) getRecv() recvAction { return nil }
func (s Send) getSend() sendAction { return s }
func (s Send) getChannel() interface{} { return s.Channel }
type empty struct {
x interface{}
}
func newEmptyInterface(e empty) reflect.Value {
return reflect.ValueOf(e).Field(0)
}
func (s Send) send() {
// With reflect.ChanValue.Send, we must match the types exactly. So, if
// s.Channel is a chan interface{} we convert s.Value to an interface{}
// first.
c := reflect.ValueOf(s.Channel)
var v reflect.Value
if iface := c.Type().Elem(); iface.Kind() == reflect.Interface && iface.NumMethod() == 0 {
v = newEmptyInterface(empty{s.Value})
} else {
v = reflect.ValueOf(s.Value)
}
c.Send(v)
}
// A Close action closes the given channel.
type Close struct {
Channel interface{}
}
func (Close) getRecv() recvAction { return nil }
func (s Close) getSend() sendAction { return s }
func (s Close) getChannel() interface{} { return s.Channel }
func (s Close) send() { reflect.ValueOf(s.Channel).Close() }
// A ReceivedUnexpected error results if no active Events match a value
// received from a channel.
type ReceivedUnexpected struct {
Value interface{}
ready []*Event
}
func (r ReceivedUnexpected) String() string {
names := make([]string, len(r.ready))
for i, v := range r.ready {
names[i] = v.name
}
return fmt.Sprintf("received unexpected value on one of the channels: %#v. Runnable events: %s", r.Value, strings.Join(names, ", "))
}
// A SetupError results if there is a error with the configuration of a set of
// Events.
type SetupError string
func (s SetupError) String() string { return string(s) }
func NewEvent(name string, predecessors []*Event, action action) *Event {
e := &Event{name, false, predecessors, action}
return e
}
// Given a set of Events, Perform repeatedly iterates over the set and finds the
// subset of ready Events (that is, all of their predecessors have
// occurred). From that subset, it pseudo-randomly selects an Event to perform.
// If the Event is a send event, the send occurs and Perform recalculates the ready
// set. If the event is a receive event, Perform waits for a value from any of the
// channels that are contained in any of the events. That value is then matched
// against the ready events. The first event that matches is considered to
// have occurred and Perform recalculates the ready set.
//
// Perform continues this until all Events have occurred.
//
// Note that uncollected goroutines may still be reading from any of the
// channels read from after Perform returns.
//
// For example, consider the problem of testing a function that reads values on
// one channel and echos them to two output channels. To test this we would
// create three events: a send event and two receive events. Each of the
// receive events must list the send event as a predecessor but there is no
// ordering between the receive events.
//
// send := NewEvent("send", nil, Send{c, 1})
// recv1 := NewEvent("recv 1", []*Event{send}, Recv{c, 1})
// recv2 := NewEvent("recv 2", []*Event{send}, Recv{c, 1})
// Perform(0, []*Event{send, recv1, recv2})
//
// At first, only the send event would be in the ready set and thus Perform will
// send a value to the input channel. Now the two receive events are ready and
// Perform will match each of them against the values read from the output channels.
//
// It would be invalid to list one of the receive events as a predecessor of
// the other. At each receive step, all the receive channels are considered,
// thus Perform may see a value from a channel that is not in the current ready
// set and fail.
func Perform(seed int64, events []*Event) (err os.Error) {
r := rand.New(rand.NewSource(seed))
channels, err := getChannels(events)
if err != nil {
return
}
multiplex := make(chan interface{})
for _, channel := range channels {
go recvValues(multiplex, channel)
}
Outer:
for {
ready, err := readyEvents(events)
if err != nil {
return err
}
if len(ready) == 0 {
// All events occurred.
break
}
event := ready[r.Intn(len(ready))]
if send := event.action.getSend(); send != nil {
send.send()
event.occurred = true
continue
}
v := <-multiplex
for _, event := range ready {
if recv := event.action.getRecv(); recv != nil && recv.recvMatch(v) {
event.occurred = true
continue Outer
}
}
return ReceivedUnexpected{v, ready}
}
return nil
}
// getChannels returns all the channels listed in any receive events.
func getChannels(events []*Event) ([]interface{}, os.Error) {
channels := make([]interface{}, len(events))
j := 0
for _, event := range events {
if recv := event.action.getRecv(); recv == nil {
continue
}
c := event.action.getChannel()
if reflect.ValueOf(c).Kind() != reflect.Chan {
return nil, SetupError("one of the channel values is not a channel")
}
duplicate := false
for _, other := range channels[0:j] {
if c == other {
duplicate = true
break
}
}
if !duplicate {
channels[j] = c
j++
}
}
return channels[0:j], nil
}
// recvValues is a multiplexing helper function. It reads values from the given
// channel repeatedly, wrapping them up as either a channelRecv or
// channelClosed structure, and forwards them to the multiplex channel.
func recvValues(multiplex chan<- interface{}, channel interface{}) {
c := reflect.ValueOf(channel)
for {
v, ok := c.Recv()
if !ok {
multiplex <- channelClosed{channel}
return
}
multiplex <- channelRecv{channel, v.Interface()}
}
}
type channelClosed struct {
channel interface{}
}
type channelRecv struct {
channel interface{}
value interface{}
}
// readyEvents returns the subset of events that are ready.
func readyEvents(events []*Event) ([]*Event, os.Error) {
ready := make([]*Event, len(events))
j := 0
eventsWaiting := false
for _, event := range events {
if event.occurred {
continue
}
eventsWaiting = true
if event.isReady() {
ready[j] = event
j++
}
}
if j == 0 && eventsWaiting {
names := make([]string, len(events))
for _, event := range events {
if event.occurred {
continue
}
names[j] = event.name
}
return nil, SetupError("dependency cycle in events. These events are waiting to run but cannot: " + strings.Join(names, ", "))
}
return ready[0:j], nil
}