2 files changed, 434 insertions, 0 deletions
diff --git a/libgo/go/testing/script/script.go b/libgo/go/testing/script/script.go
new file mode 100644
index 000000000..11f5a7425
--- /dev/null
+++ b/libgo/go/testing/script/script.go
@@ -0,0 +1,359 @@
+// 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 }
+
+type empty struct {
+	x interface{}
+}
+
+func newEmptyInterface(e empty) reflect.Value {
+	return reflect.NewValue(e).(*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(empty{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
+}
diff --git a/libgo/go/testing/script/script_test.go b/libgo/go/testing/script/script_test.go
new file mode 100644
index 000000000..e9ab142c2
--- /dev/null
+++ b/libgo/go/testing/script/script_test.go
@@ -0,0 +1,75 @@
+// 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
+
+import (
+	"testing"
+)
+
+func TestNoop(t *testing.T) {
+	err := Perform(0, nil)
+	if err != nil {
+		t.Errorf("Got error: %s", err)
+	}
+}
+
+func TestSimple(t *testing.T) {
+	c := make(chan int)
+	defer close(c)
+
+	a := NewEvent("send", nil, Send{c, 1})
+	b := NewEvent("recv", []*Event{a}, Recv{c, 1})
+
+	err := Perform(0, []*Event{a, b})
+	if err != nil {
+		t.Errorf("Got error: %s", err)
+	}
+}
+
+func TestFail(t *testing.T) {
+	c := make(chan int)
+	defer close(c)
+
+	a := NewEvent("send", nil, Send{c, 2})
+	b := NewEvent("recv", []*Event{a}, Recv{c, 1})
+
+	err := Perform(0, []*Event{a, b})
+	if err == nil {
+		t.Errorf("Failed to get expected error")
+	} else if _, ok := err.(ReceivedUnexpected); !ok {
+		t.Errorf("Error returned was of the wrong type: %s", err)
+	}
+}
+
+func TestClose(t *testing.T) {
+	c := make(chan int)
+
+	a := NewEvent("close", nil, Close{c})
+	b := NewEvent("closed", []*Event{a}, Closed{c})
+
+	err := Perform(0, []*Event{a, b})
+	if err != nil {
+		t.Errorf("Got error: %s", err)
+	}
+}
+
+func matchOne(v interface{}) bool {
+	if i, ok := v.(int); ok && i == 1 {
+		return true
+	}
+	return false
+}
+
+func TestRecvMatch(t *testing.T) {
+	c := make(chan int)
+
+	a := NewEvent("send", nil, Send{c, 1})
+	b := NewEvent("recv", []*Event{a}, RecvMatch{c, matchOne})
+
+	err := Perform(0, []*Event{a, b})
+	if err != nil {
+		t.Errorf("Got error: %s", err)
+	}
+}