Subversion Repositories openrisc

// 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 aids in the testing of code that uses channels.
package script

import (
        "fmt"
        "math/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.ValueOf(e).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.ValueOf(s.Channel)
        var v reflect.Value
        if iface := c.Type().Elem(); iface.Kind() == reflect.Interface && iface.NumMethod() == 0 {
                v = newEmptyInterface(empty{s.Value})
        } else {
                v = reflect.ValueOf(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.ValueOf(s.Channel).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) Error() 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) Error() 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 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{}, 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 reflect.ValueOf(c).Kind() != reflect.Chan {
                        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.ValueOf(channel)

        for {
                v, ok := c.Recv()
                if !ok {
                        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, 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
}