Add testing/script.

R=rsc, r
CC=go-dev
http://go/go-review/1016001

1 files changed, 389 insertions, 0 deletions

diff --git a/src/pkg/testing/script/script.go b/src/pkg/testing/script/script.go
new file mode 100644
index 000000000..71e7cdca4
--- /dev/null
+++ b/src/pkg/testing/script/script.go
@@ -0,0 +1,389 @@
+// 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.
+
+// This package 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;
+}
+
+func newEmptyInterface(args ...) reflect.Value {
+	return reflect.NewValue(args).(*reflect.StructValue).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.NewValue(s.Channel).(*reflect.ChanValue);
+	var v reflect.Value;
+	if iface, ok := c.Type().(*reflect.ChanType).Elem().(*reflect.InterfaceType); ok && iface.NumMethod() == 0 {
+		v = newEmptyInterface(s.Value);
+	} else {
+		v = reflect.NewValue(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.NewValue(s.Channel).(*reflect.ChanValue).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 _, ok := reflect.NewValue(c).(*reflect.ChanValue); !ok {
+			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.NewValue(channel).(*reflect.ChanValue);
+
+	for {
+		v := c.Recv();
+		if c.Closed() {
+			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;
+}