script.go

// 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"
	"math/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) Error() 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) Error() 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 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{}, 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, 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
}