README
Documentation
¶
Overview ¶
Package gsim provides the ability to exhaustively iterate through every permutation of a graph, to facilitate exhaustive simulation.
The idea is that you might be trying to simulate some sort of concurrent system. Various events can occur within the system as a whole but there are constraints on the possible order in which things can occur. These constraints you can describe as a graph (or series of graphs). This package will then exhaustively produce every possible serial order of events.
What you do with such permutations is entirely up to you. One idea is you might consider those events as instructions, and write an interpreter to process those instructions. Then at the end, you can check to see if goals have been met and invariants kept. If they have been, you have performed a model check that with any valid sequence of instructions as generated from the graph, your algorithm is correct.
An alternative use is for testing: the permutation represents the order of events which you send to some black-box system to be tested. You then write your own simple interpreter, if necessary, and then perform some sort of equivalence checking on the final states of the black-box system and your simple interpreter.
A fair amount of effort has been spent in trying to keep the permutation generator both fast, and with minimal memory use. That said, in all likelihood it will never compete with other tools such as TLA+, but it allows you to write your models in Go and thus there'll be less of a gap between your model code and your real implementation.
See https://github.com/msackman/gsim/blob/master/main/main.go for examples.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( NoChange = &noChange{} MakeAvailable = &makeAvailable{} Inhibit = &inhibit{} )
var AvailableAnyCallback = &availableAnyCallback{}
The AvailableAnyCallback is the default callback and will always return MakeAvailable. This means as soon as at least one incoming edge has been reached, the node becomes available for selection.
var InhibitAnyCallback = &inhibitAnyCallback{}
The InhibitAnyCallback is the inhibit equivalent to AvailableAnyCallback. It returns Inhibit as soon as at least one incoming edge has been reached.
Functions ¶
This section is empty.
Types ¶
type AvailableAllCallback ¶
type AvailableAllCallback GraphNodeCallback
The AvailableAllCallback returns MakeAvailable only when all of the nodes supplied to the constructor are found in the reached incoming edges. It never returns Inhibit.
func NewAvailableAllCallback ¶
func NewAvailableAllCallback(required ...*GraphNode) AvailableAllCallback
type CombinationCallback ¶
type CombinationCallback struct {
// contains filtered or unexported fields
}
The CombinationCallback allows you to attach several callbacks to a graphnode. This is very useful for more complex and layered logic surrounding when a node becomes available for selection or inhibited. Each callback produces a GraphNodeStateChange answer, and it is then up to the combiner function to combine all those answers. The combiner is the same as the function in a fold: it is fed with the current accumulated value, and the new value, and asked to produce a newer accumulated value. The combiner can indicate to stop iteration through the callbacks (i.e. short-circuiting) if it decides it's reached a result which cannot change. The accumulator is initiated to NoChange. It is in fact perfectly possible to have combinations of combinations, should you really need to!
func NewCombinationCallback ¶
func NewCombinationCallback(combiner CombinationCallbackCombiner) *CombinationCallback
func (*CombinationCallback) AddCallback ¶
func (cc *CombinationCallback) AddCallback(callback GraphNodeCallback)
func (*CombinationCallback) IncomingEdgesReached ¶
func (cc *CombinationCallback) IncomingEdgesReached(node *GraphNode, reached []*GraphNode) GraphNodeStateChange
type CombinationCallbackCombiner ¶
type CombinationCallbackCombiner func(node *GraphNode, reached []*GraphNode, acc GraphNodeStateChange, curCallback GraphNodeCallback, callbackResult GraphNodeStateChange) (newAcc GraphNodeStateChange, stop bool)
type GraphNode ¶
type GraphNode struct {
// The value you've provided to this GraphNode.
Value interface{}
// The outgoing edges from this node. Treat this field as read-only
// and use the AddEdgeTo method to add edges.
Out []*GraphNode
// The incoming edges from this node. Treat this field as read-only
// and use the AddEdgeTo method to add edges.
In []*GraphNode
// The callback is invoked when the node is not inhibited and an
// additional incoming edge is reached. The callback controls when
// the node becomes eligible for selection in the permutation, and
// when it is excluded from selection.
Callback GraphNodeCallback
}
GraphNodes allow you to construct arbitrary graphs which can be used to describe the dependencies between different events occurring, for example. As usual with graph libraries, create all the nodes you need first, and then link them together with edges.
Permutations generated will be lists of GraphNodes. Access the value you supplied through the Value field.
Each generated permutation will contain each node no more than once. Cycles in the graph are eliminated. Edges between nodes can make the target node eligible for selection in the permutation, or excluded from selection.
When generating the graph programmatically, you must also ensure even your generation of the graph is deterministic - i.e. the order in which edges are added to nodes should be the same for multiple iterations. If they are not, then you will find permutation numbers differ between iterations.
func NewGraphNode ¶
func NewGraphNode(value interface{}) *GraphNode
Construct a new GraphNode. The node will start with no edges, and Callback is AvailableAnyCallback.
type GraphNodeCallback ¶
type GraphNodeCallback interface {
IncomingEdgesReached(*GraphNode, []*GraphNode) GraphNodeStateChange
}
type GraphNodeStateChange ¶
type GraphNodeStateChange interface {
// contains filtered or unexported methods
}
func InhibitThenAvailableCombiner ¶
func InhibitThenAvailableCombiner(node *GraphNode, reached []*GraphNode, acc GraphNodeStateChange, curCallback GraphNodeCallback, callbackResult GraphNodeStateChange) (newAcc GraphNodeStateChange, stop bool)
InhibitThenAvailableCombiner is a CombinationCallbackCombiner. Its semantics are that if any callback returns Inhibit, then the result is Inhibit. If no callback returns Inhibit, and at least one callback returns MakeAvailable then the result in MakeAvailable. Otherwise the result is NoChange.
type InhibitAllCallback ¶
type InhibitAllCallback GraphNodeCallback
The InhibitAllCallback is the inhibit equivalent to AvailableAllCallback. It returns Inhibit only when all of the nodes supplied to the constructor are found in the reached incoming edges. It never returns MakeAvailable.
func NewInhibitAllCallback ¶
func NewInhibitAllCallback(required ...*GraphNode) InhibitAllCallback
type OptionGenerator ¶
type OptionGenerator interface {
// Generate is provided with the previously-chosen option, and is
// required to return the set of options now available as the next
// element in the permutation. OptionGenerators are expected to be
// stateful. Generate must return an empty list for permutation
// generation to terminate.
Generate(interface{}) []interface{}
// Clone is used during permutation generation. If the
// OptionGenerator is stateful then Clone must return a fresh
// OptionGenerator which shares no mutable state with the receiver
// of Clone.
Clone() OptionGenerator
}
The OptionGenerator is responsible for generating the next available possible paths from each permutation prefix. Two implementations of OptionGenerator are provided: simplePermutation and graphPermutation. If neither are sufficient for your needs then you'll want to implement OptionGenerator yourself.
If you do implement OptionGenerator yourself, you must ensure it is entirely deterministic. So do not rely on iteration order of maps and so forth.
func NewGraphPermutation ¶
func NewGraphPermutation(startingNode ...*GraphNode) OptionGenerator
Create a OptionGenerator for the given graphs. Note the starting nodes may both be from the same graph (useful if you don't know what the first event will be), or from multiple disjoint graphs, or any combination.
func NewSimplePermutation ¶
func NewSimplePermutation(elems []interface{}) OptionGenerator
SimplePermutation is an example implementation of OptionGenerator which implements a plain permutation with no dependencies between any values. For example, with the elems a,b,c, every permutation will be found: a,b,c; a,c,b; b,a,c; b,c,a; c,a,b; c,b,a
type PermutationConsumer ¶
type PermutationConsumer interface {
// Clone is used only by Permutations.ForEachPar and is called
// once for each go-routine which will be supplying permutations
// to the PermutationConsumer. Through this, state can be
// duplicated so that the consumer can be stateful and safe to
// drive from multiple go-routines.
Clone() PermutationConsumer
// This function called once for each permutation generated.
Consume(*big.Int, []interface{})
}
Instances of PermutationConsumer may be supplied to the Permutations iteration functions: ForEach and ForEachPar.
type Permutations ¶
type Permutations node
Permutations allows you to interate through the available permutations, and extract specific permutations.
func BuildPermutations ¶
func BuildPermutations(gen OptionGenerator) *Permutations
Construct a Permutations from an OptionGenerator.
func (*Permutations) ForEach ¶
func (p *Permutations) ForEach(f PermutationConsumer)
Iterate through every permutation in the current go-routine. No parallelism occurs. The function f.Consume is invoked once for every permutation. It is supplied with the permutation number, and the permutation itself. These arguments should be considered read-only. If you mutate the permutation number or permutation then behaviour is undefined.
func (*Permutations) ForEachPar ¶
func (p *Permutations) ForEachPar(batchSize int, f PermutationConsumer)
Iterate through every permutation and use concurrency. A number of go-routines will be spawned appropriate for the current value of GOMAXPROCS. These go-routines will be fed batches of permutations and then invoke f.Consume for each permutation. It's your responsibility to make sure f is safe to be run concurrently from multiple go-routines (see PermutationConsumer.Clone to see how stateful consumers can be built).
If the batchsize is very low, then the generation of permutations will thrash CPU due to contention for locks on channels. If your processing of each permutation is very quick, then high numbers (e.g. 8192) can help to keep your CPU busy. If your processing of each permutation is less quick then lower numbers will avoid memory ballooning. Some trial and error may be worthwhile to find a good number for your computer, but 2048 is a sensible place to start.
func (*Permutations) Permutation ¶
func (p *Permutations) Permutation(permNum *big.Int) []interface{}
Every permutation has a unique number, which is supplied to the function passed to both of the iteration functions in Permutations. If you need to generate specific permutations, those numbers can be provided to Permutation, which will generate the exact same permutation. Note that iterating through a range of permutation numbers and repeatedly calling Permutation is slower than using either of the iterator functions.
Source Files
Directories