Source file src/pkg/testing/script/script.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Package script aids in the testing of code that uses channels.
     6	package script
     7	
     8	import (
     9		"fmt"
    10		"os"
    11		"rand"
    12		"reflect"
    13		"strings"
    14	)
    15	
    16	// An Event is an element in a partially ordered set that either sends a value
    17	// to a channel or expects a value from a channel.
    18	type Event struct {
    19		name         string
    20		occurred     bool
    21		predecessors []*Event
    22		action       action
    23	}
    24	
    25	type action interface {
    26		// getSend returns nil if the action is not a send action.
    27		getSend() sendAction
    28		// getRecv returns nil if the action is not a receive action.
    29		getRecv() recvAction
    30		// getChannel returns the channel that the action operates on.
    31		getChannel() interface{}
    32	}
    33	
    34	type recvAction interface {
    35		recvMatch(interface{}) bool
    36	}
    37	
    38	type sendAction interface {
    39		send()
    40	}
    41	
    42	// isReady returns true if all the predecessors of an Event have occurred.
    43	func (e Event) isReady() bool {
    44		for _, predecessor := range e.predecessors {
    45			if !predecessor.occurred {
    46				return false
    47			}
    48		}
    49	
    50		return true
    51	}
    52	
    53	// A Recv action reads a value from a channel and uses reflect.DeepMatch to
    54	// compare it with an expected value.
    55	type Recv struct {
    56		Channel  interface{}
    57		Expected interface{}
    58	}
    59	
    60	func (r Recv) getRecv() recvAction { return r }
    61	
    62	func (Recv) getSend() sendAction { return nil }
    63	
    64	func (r Recv) getChannel() interface{} { return r.Channel }
    65	
    66	func (r Recv) recvMatch(chanEvent interface{}) bool {
    67		c, ok := chanEvent.(channelRecv)
    68		if !ok || c.channel != r.Channel {
    69			return false
    70		}
    71	
    72		return reflect.DeepEqual(c.value, r.Expected)
    73	}
    74	
    75	// A RecvMatch action reads a value from a channel and calls a function to
    76	// determine if the value matches.
    77	type RecvMatch struct {
    78		Channel interface{}
    79		Match   func(interface{}) bool
    80	}
    81	
    82	func (r RecvMatch) getRecv() recvAction { return r }
    83	
    84	func (RecvMatch) getSend() sendAction { return nil }
    85	
    86	func (r RecvMatch) getChannel() interface{} { return r.Channel }
    87	
    88	func (r RecvMatch) recvMatch(chanEvent interface{}) bool {
    89		c, ok := chanEvent.(channelRecv)
    90		if !ok || c.channel != r.Channel {
    91			return false
    92		}
    93	
    94		return r.Match(c.value)
    95	}
    96	
    97	// A Closed action matches if the given channel is closed. The closing is
    98	// treated as an event, not a state, thus Closed will only match once for a
    99	// given channel.
   100	type Closed struct {
   101		Channel interface{}
   102	}
   103	
   104	func (r Closed) getRecv() recvAction { return r }
   105	
   106	func (Closed) getSend() sendAction { return nil }
   107	
   108	func (r Closed) getChannel() interface{} { return r.Channel }
   109	
   110	func (r Closed) recvMatch(chanEvent interface{}) bool {
   111		c, ok := chanEvent.(channelClosed)
   112		if !ok || c.channel != r.Channel {
   113			return false
   114		}
   115	
   116		return true
   117	}
   118	
   119	// A Send action sends a value to a channel. The value must match the
   120	// type of the channel exactly unless the channel if of type chan interface{}.
   121	type Send struct {
   122		Channel interface{}
   123		Value   interface{}
   124	}
   125	
   126	func (Send) getRecv() recvAction { return nil }
   127	
   128	func (s Send) getSend() sendAction { return s }
   129	
   130	func (s Send) getChannel() interface{} { return s.Channel }
   131	
   132	type empty struct {
   133		x interface{}
   134	}
   135	
   136	func newEmptyInterface(e empty) reflect.Value {
   137		return reflect.ValueOf(e).Field(0)
   138	}
   139	
   140	func (s Send) send() {
   141		// With reflect.ChanValue.Send, we must match the types exactly. So, if
   142		// s.Channel is a chan interface{} we convert s.Value to an interface{}
   143		// first.
   144		c := reflect.ValueOf(s.Channel)
   145		var v reflect.Value
   146		if iface := c.Type().Elem(); iface.Kind() == reflect.Interface && iface.NumMethod() == 0 {
   147			v = newEmptyInterface(empty{s.Value})
   148		} else {
   149			v = reflect.ValueOf(s.Value)
   150		}
   151		c.Send(v)
   152	}
   153	
   154	// A Close action closes the given channel.
   155	type Close struct {
   156		Channel interface{}
   157	}
   158	
   159	func (Close) getRecv() recvAction { return nil }
   160	
   161	func (s Close) getSend() sendAction { return s }
   162	
   163	func (s Close) getChannel() interface{} { return s.Channel }
   164	
   165	func (s Close) send() { reflect.ValueOf(s.Channel).Close() }
   166	
   167	// A ReceivedUnexpected error results if no active Events match a value
   168	// received from a channel.
   169	type ReceivedUnexpected struct {
   170		Value interface{}
   171		ready []*Event
   172	}
   173	
   174	func (r ReceivedUnexpected) String() string {
   175		names := make([]string, len(r.ready))
   176		for i, v := range r.ready {
   177			names[i] = v.name
   178		}
   179		return fmt.Sprintf("received unexpected value on one of the channels: %#v. Runnable events: %s", r.Value, strings.Join(names, ", "))
   180	}
   181	
   182	// A SetupError results if there is a error with the configuration of a set of
   183	// Events.
   184	type SetupError string
   185	
   186	func (s SetupError) String() string { return string(s) }
   187	
   188	func NewEvent(name string, predecessors []*Event, action action) *Event {
   189		e := &Event{name, false, predecessors, action}
   190		return e
   191	}
   192	
   193	// Given a set of Events, Perform repeatedly iterates over the set and finds the
   194	// subset of ready Events (that is, all of their predecessors have
   195	// occurred). From that subset, it pseudo-randomly selects an Event to perform.
   196	// If the Event is a send event, the send occurs and Perform recalculates the ready
   197	// set. If the event is a receive event, Perform waits for a value from any of the
   198	// channels that are contained in any of the events. That value is then matched
   199	// against the ready events. The first event that matches is considered to
   200	// have occurred and Perform recalculates the ready set.
   201	//
   202	// Perform continues this until all Events have occurred.
   203	//
   204	// Note that uncollected goroutines may still be reading from any of the
   205	// channels read from after Perform returns.
   206	//
   207	// For example, consider the problem of testing a function that reads values on
   208	// one channel and echos them to two output channels. To test this we would
   209	// create three events: a send event and two receive events. Each of the
   210	// receive events must list the send event as a predecessor but there is no
   211	// ordering between the receive events.
   212	//
   213	//  send := NewEvent("send", nil, Send{c, 1})
   214	//  recv1 := NewEvent("recv 1", []*Event{send}, Recv{c, 1})
   215	//  recv2 := NewEvent("recv 2", []*Event{send}, Recv{c, 1})
   216	//  Perform(0, []*Event{send, recv1, recv2})
   217	//
   218	// At first, only the send event would be in the ready set and thus Perform will
   219	// send a value to the input channel. Now the two receive events are ready and
   220	// Perform will match each of them against the values read from the output channels.
   221	//
   222	// It would be invalid to list one of the receive events as a predecessor of
   223	// the other. At each receive step, all the receive channels are considered,
   224	// thus Perform may see a value from a channel that is not in the current ready
   225	// set and fail.
   226	func Perform(seed int64, events []*Event) (err os.Error) {
   227		r := rand.New(rand.NewSource(seed))
   228	
   229		channels, err := getChannels(events)
   230		if err != nil {
   231			return
   232		}
   233		multiplex := make(chan interface{})
   234		for _, channel := range channels {
   235			go recvValues(multiplex, channel)
   236		}
   237	
   238	Outer:
   239		for {
   240			ready, err := readyEvents(events)
   241			if err != nil {
   242				return err
   243			}
   244	
   245			if len(ready) == 0 {
   246				// All events occurred.
   247				break
   248			}
   249	
   250			event := ready[r.Intn(len(ready))]
   251			if send := event.action.getSend(); send != nil {
   252				send.send()
   253				event.occurred = true
   254				continue
   255			}
   256	
   257			v := <-multiplex
   258			for _, event := range ready {
   259				if recv := event.action.getRecv(); recv != nil && recv.recvMatch(v) {
   260					event.occurred = true
   261					continue Outer
   262				}
   263			}
   264	
   265			return ReceivedUnexpected{v, ready}
   266		}
   267	
   268		return nil
   269	}
   270	
   271	// getChannels returns all the channels listed in any receive events.
   272	func getChannels(events []*Event) ([]interface{}, os.Error) {
   273		channels := make([]interface{}, len(events))
   274	
   275		j := 0
   276		for _, event := range events {
   277			if recv := event.action.getRecv(); recv == nil {
   278				continue
   279			}
   280			c := event.action.getChannel()
   281			if reflect.ValueOf(c).Kind() != reflect.Chan {
   282				return nil, SetupError("one of the channel values is not a channel")
   283			}
   284	
   285			duplicate := false
   286			for _, other := range channels[0:j] {
   287				if c == other {
   288					duplicate = true
   289					break
   290				}
   291			}
   292	
   293			if !duplicate {
   294				channels[j] = c
   295				j++
   296			}
   297		}
   298	
   299		return channels[0:j], nil
   300	}
   301	
   302	// recvValues is a multiplexing helper function. It reads values from the given
   303	// channel repeatedly, wrapping them up as either a channelRecv or
   304	// channelClosed structure, and forwards them to the multiplex channel.
   305	func recvValues(multiplex chan<- interface{}, channel interface{}) {
   306		c := reflect.ValueOf(channel)
   307	
   308		for {
   309			v, ok := c.Recv()
   310			if !ok {
   311				multiplex <- channelClosed{channel}
   312				return
   313			}
   314	
   315			multiplex <- channelRecv{channel, v.Interface()}
   316		}
   317	}
   318	
   319	type channelClosed struct {
   320		channel interface{}
   321	}
   322	
   323	type channelRecv struct {
   324		channel interface{}
   325		value   interface{}
   326	}
   327	
   328	// readyEvents returns the subset of events that are ready.
   329	func readyEvents(events []*Event) ([]*Event, os.Error) {
   330		ready := make([]*Event, len(events))
   331	
   332		j := 0
   333		eventsWaiting := false
   334		for _, event := range events {
   335			if event.occurred {
   336				continue
   337			}
   338	
   339			eventsWaiting = true
   340			if event.isReady() {
   341				ready[j] = event
   342				j++
   343			}
   344		}
   345	
   346		if j == 0 && eventsWaiting {
   347			names := make([]string, len(events))
   348			for _, event := range events {
   349				if event.occurred {
   350					continue
   351				}
   352				names[j] = event.name
   353			}
   354	
   355			return nil, SetupError("dependency cycle in events. These events are waiting to run but cannot: " + strings.Join(names, ", "))
   356		}
   357	
   358		return ready[0:j], nil
   359	}
The Go Programming Language

Source file src/pkg/testing/script/script.go
