From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libgo/go/testing/script/script.go | 359 +++++++++++++++++++++++++++++++++ libgo/go/testing/script/script_test.go | 75 +++++++ 2 files changed, 434 insertions(+) create mode 100644 libgo/go/testing/script/script.go create mode 100644 libgo/go/testing/script/script_test.go (limited to 'libgo/go/testing/script') 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) + } +} -- cgit v1.2.3