diff options
| -rw-r--r-- | src/pkg/Make.deps | 12 | ||||
| -rw-r--r-- | src/pkg/Makefile | 2 | ||||
| -rw-r--r-- | src/pkg/testing/script/Makefile | 11 | ||||
| -rw-r--r-- | src/pkg/testing/script/script.go | 389 | ||||
| -rw-r--r-- | src/pkg/testing/script/script_test.go | 75 |
5 files changed, 484 insertions, 5 deletions
diff --git a/src/pkg/Make.deps b/src/pkg/Make.deps index 614f48b66..94f42ed3a 100644 --- a/src/pkg/Make.deps +++ b/src/pkg/Make.deps @@ -5,8 +5,8 @@ bignum.install: fmt.install bufio.install: io.install os.install strconv.install utf8.install bytes.install: os.install unicode.install utf8.install compress/flate.install: bufio.install bytes.install io.install math.install os.install sort.install strconv.install -compress/gzip.install: bufio.install compress/flate.install hash.install hash/crc32.install io.install os.install -compress/zlib.install: bufio.install compress/flate.install hash.install hash/adler32.install io.install os.install +compress/gzip.install: bufio.install compress/flate.install hash/crc32.install hash.install io.install os.install +compress/zlib.install: bufio.install compress/flate.install hash/adler32.install hash.install io.install os.install container/heap.install: sort.install container/list.install: container/ring.install: @@ -20,7 +20,7 @@ crypto/sha1.install: hash.install os.install crypto/subtle.install: debug/dwarf.install: encoding/binary.install os.install strconv.install debug/macho.install: bytes.install debug/dwarf.install encoding/binary.install fmt.install io.install os.install strconv.install -debug/elf.install: debug/dwarf.install encoding/binary.install fmt.install io.install os.install strconv.install +debug/elf.install: bytes.install debug/dwarf.install encoding/binary.install fmt.install io.install os.install strconv.install debug/gosym.install: encoding/binary.install fmt.install os.install strconv.install strings.install debug/proc.install: container/vector.install fmt.install io.install os.install runtime.install strconv.install strings.install sync.install syscall.install ebnf.install: container/vector.install go/scanner.install go/token.install os.install strconv.install unicode.install utf8.install @@ -28,6 +28,7 @@ encoding/ascii85.install: bytes.install io.install os.install strconv.install encoding/base64.install: bytes.install io.install os.install strconv.install encoding/binary.install: io.install math.install os.install reflect.install encoding/git85.install: bytes.install io.install os.install strconv.install +encoding/hex.install: os.install strconv.install strings.install encoding/pem.install: bytes.install encoding/base64.install strings.install exec.install: os.install strings.install exp/datafmt.install: bytes.install container/vector.install fmt.install go/scanner.install go/token.install io.install os.install reflect.install runtime.install strconv.install strings.install @@ -48,7 +49,7 @@ hash/adler32.install: hash.install os.install hash/crc32.install: hash.install os.install http.install: bufio.install bytes.install container/vector.install fmt.install io.install log.install net.install os.install path.install strconv.install strings.install utf8.install image.install: -image/png.install: bufio.install compress/zlib.install hash.install hash/crc32.install image.install io.install os.install strconv.install +image/png.install: bufio.install compress/zlib.install hash/crc32.install hash.install image.install io.install os.install strconv.install io.install: bytes.install os.install sort.install strings.install sync.install json.install: bytes.install container/vector.install fmt.install math.install reflect.install strconv.install strings.install utf8.install log.install: fmt.install io.install os.install runtime.install time.install @@ -60,7 +61,7 @@ os.install: once.install syscall.install path.install: io.install os.install strings.install rand.install: math.install reflect.install: runtime.install strconv.install -regexp.install: bytes.install container/vector.install io.install os.install runtime.install utf8.install +regexp.install: bytes.install container/vector.install io.install os.install utf8.install rpc.install: bufio.install fmt.install gob.install http.install io.install log.install net.install os.install reflect.install sort.install strings.install sync.install template.install unicode.install utf8.install runtime.install: sort.install: @@ -73,6 +74,7 @@ template.install: bytes.install container/vector.install fmt.install io.install testing.install: flag.install fmt.install os.install runtime.install utf8.install testing/iotest.install: bytes.install io.install log.install os.install testing/quick.install: flag.install fmt.install math.install os.install rand.install reflect.install strings.install +testing/script.install: fmt.install os.install rand.install reflect.install strings.install time.install: io.install once.install os.install syscall.install unicode.install: utf8.install: unicode.install diff --git a/src/pkg/Makefile b/src/pkg/Makefile index baf2122c8..1be6ff733 100644 --- a/src/pkg/Makefile +++ b/src/pkg/Makefile @@ -42,6 +42,7 @@ DIRS=\ encoding/base64\ encoding/binary\ encoding/git85\ + encoding/hex\ encoding/pem\ exec\ exp/datafmt\ @@ -87,6 +88,7 @@ DIRS=\ testing\ testing/iotest\ testing/quick\ + testing/script\ time\ unicode\ utf8\ diff --git a/src/pkg/testing/script/Makefile b/src/pkg/testing/script/Makefile new file mode 100644 index 000000000..1b4882d56 --- /dev/null +++ b/src/pkg/testing/script/Makefile @@ -0,0 +1,11 @@ +# 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. + +include $(GOROOT)/src/Make.$(GOARCH) + +TARG=testing/script +GOFILES=\ + script.go\ + +include $(GOROOT)/src/Make.pkg 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; +} diff --git a/src/pkg/testing/script/script_test.go b/src/pkg/testing/script/script_test.go new file mode 100644 index 000000000..a1c6f28a7 --- /dev/null +++ b/src/pkg/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); + } +} |