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

}