modelchecker

package
v0.3.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 17, 2025 License: Apache-2.0 Imports: 32 Imported by: 0

Documentation

Overview

Package modelchecker implements the model checker for the FizzBuzz program. It is based on the Starlark interpreter for the python part of the code. For the interpreter to implement the model checker, we need to simulate parallel universe. Every time, there is a non-deterministic choice, we need to fork the universe and continue the execution in both the universes with the different choices. Each universe is represented by a process. Each process has a heap and multiple threads. Each thread has a stack of call frames. Each call frame has a program counter and scope (with nesting). The heap is shared across all the threads in the process. Duplicate detection: Two threads are same if they have the same stack of call frames Two processes are same if they have the same heap and same threads.

Index

Constants

View Source
const (
	ActionsWithMultipleBlocks = `` /* 3732-byte string literal not displayed */

)

Variables

This section is empty.

Functions

func CheckAssertion

func CheckAssertion(process *Process, invariant *ast.Invariant, index int) bool

func CheckFastLiveness

func CheckFastLiveness(allNodes []*Node) ([]*Link, *InvariantPosition)

func CheckInvariant

func CheckInvariant(process *Process, invariant *ast.Invariant) bool

func CheckInvariants

func CheckInvariants(process *Process) map[int][]int

func CheckLivenessSccAlwaysEventually

func CheckLivenessSccAlwaysEventually(nodes []*Node, invPos InvariantPosition) (bool, error)

func CheckRefinement added in v0.2.0

func CheckRefinement(process *Process, refinement *ast.Refinement, joinHashes JoinHashes) bool

func CheckStrictLiveness

func CheckStrictLiveness(node *Node, nodes []*Node) ([]*Link, *InvariantPosition)

func CheckTransitionAssertion

func CheckTransitionAssertion(process *Process, invariant *ast.Invariant, index int) bool

func CheckTransitionInvariants

func CheckTransitionInvariants(process *Process) map[int][]int

func CloneDict

func CloneDict(oldDict starlark.StringDict, refs map[starlark.Value]starlark.Value, permutations map[lib.SymmetricValue][]lib.SymmetricValue, alt int) starlark.StringDict

func ContainsInt

func ContainsInt(skipstmts []int, i int) bool

func CopyDict

CopyDict copies values `from` to `to` overriding existing values. If the `to` is nil, creates a new dict.

func DeepCopyBuiltIn

func DeepCopyBuiltIn(thread *starlark.Thread, fn *starlark.Builtin, args starlark.Tuple, kwargs []starlark.Tuple) (starlark.Value, error)

func EndOfBlock

func EndOfBlock(path string) string

func ExecFunction added in v0.2.0

func ExecFunction(process *Process, name string) starlark.Value

func GenerateCommunicationGraph

func GenerateCommunicationGraph(messages []string) string

func GenerateDotFile

func GenerateDotFile(node *Node, visited map[*Node]bool) string

func GenerateErrorPathProtoOfJson

func GenerateErrorPathProtoOfJson(errorPath []*Link, pathPrefix string) ([]string, []string, error)

func GenerateFailurePath

func GenerateFailurePath(nodes []*Link, name string, invariant *InvariantPosition) string

func GenerateFailurePathHtml added in v0.2.0

func GenerateFailurePathHtml(srcFileName string, failurePath []*Link, invariant *InvariantPosition, outDir string) error

GenerateFailurePathHtml creates an HTML file showing differences between adjacent failurePath Links

func GenerateProtoOfJson

func GenerateProtoOfJson(nodes []*Node, pathPrefix string) ([]string, []string, error)

func GetAllNodes

func GetAllNodes(root *Node, maxActions int64) ([]*Node, []string, *Node, int)

func GetFieldByPath

func GetFieldByPath(msg proto.Message, path string) *reflect.Value

func GetNextFieldPath

func GetNextFieldPath(msg proto.Message, path string) (string, *reflect.Value)

func GetProtoFieldByPath

func GetProtoFieldByPath(file *ast.File, location string) proto.Message

func GetStringFieldByPath

func GetStringFieldByPath(file *ast.File, location string) (string, bool)

func HandleModules

func HandleModules(path string) map[string]starlark.Value

func LoadModule

func LoadModule(moduleFile string) starlark.StringDict

func MapRoleValuesInOrder

func MapRoleValuesInOrder(m map[starlark.Value]starlark.Value, oldList []*lib.Role) []*lib.Role

MapRoleValuesInOrder returns the values of the map m. The values will be in an indeterminate order.

func NewDictFromStringDict

func NewDictFromStringDict(vals starlark.StringDict) *starlark.Dict

func PanicIfFalse

func PanicIfFalse(ok bool, msg string)

func PanicOnError

func PanicOnError(err error)

func ParentBlockPath

func ParentBlockPath(path string) string

func ReadOptionsFromYaml

func ReadOptionsFromYaml(filename string) (*proto.StateSpaceOptions, error)

func ReadOptionsFromYamlString

func ReadOptionsFromYamlString(contents string) (*proto.StateSpaceOptions, error)

func RemoveLastBlock

func RemoveLastBlock(path string) string

func RemoveLastForStmt

func RemoveLastForStmt(path string) string

func RemoveLastLoop

func RemoveLastLoop(path string) string

func RemoveLastLoopBlock

func RemoveLastLoopBlock(path string) string

func RemoveLastSegment

func RemoveLastSegment(path string, substr string) string

func RemoveLastWhileStmt

func RemoveLastWhileStmt(path string) string

func RemoveMergeNodes

func RemoveMergeNodes(root *Node)

func StringDictToJson

func StringDictToJson(stringDict starlark.StringDict) ([]byte, error)

func StringDictToJsonRetainType

func StringDictToJsonRetainType(strDict starlark.StringDict) ([]byte, error)

func StringDictToJsonString

func StringDictToJsonString(stringDict starlark.StringDict) string

func StringDictToMap

func StringDictToMap(stringDict starlark.StringDict) map[string]string

Types

type CallFrame

type CallFrame struct {
	// FileIndex is the ast.FileIndex that this frame is executing.
	FileIndex int

	// Name is the full path of the function/action being executed.
	Name string
	// contains filtered or unexported fields
}

func (*CallFrame) Clone

func (c *CallFrame) Clone(refs map[starlark.Value]starlark.Value, permutations map[lib.SymmetricValue][]lib.SymmetricValue, alt int) (*CallFrame, error)

func (*CallFrame) HashCode

func (c *CallFrame) HashCode() string

func (*CallFrame) MarshalJSON

func (c *CallFrame) MarshalJSON() ([]byte, error)

type CallStack

type CallStack struct {
	*lib.Stack[*CallFrame]
}

func NewCallStack

func NewCallStack() *CallStack

func (*CallStack) Clone

func (*CallStack) HashCode

func (s *CallStack) HashCode() string

type ChannelMessage

type ChannelMessage struct {
	// contains filtered or unexported fields
}

func (*ChannelMessage) Clone

func (cm *ChannelMessage) Clone(refs map[starlark.Value]starlark.Value, permutations map[lib.SymmetricValue][]lib.SymmetricValue, alt int) *ChannelMessage

func (*ChannelMessage) Frame

func (cm *ChannelMessage) Frame() *CallFrame

func (*ChannelMessage) Function

func (cm *ChannelMessage) Function() string

func (*ChannelMessage) HashCode

func (cm *ChannelMessage) HashCode() string

func (*ChannelMessage) MarshalJSON

func (cm *ChannelMessage) MarshalJSON() ([]byte, error)

func (*ChannelMessage) Params

func (cm *ChannelMessage) Params() starlark.StringDict

func (*ChannelMessage) Receiver

func (cm *ChannelMessage) Receiver() string

func (*ChannelMessage) String

func (cm *ChannelMessage) String() string

type CodeSnippet

type CodeSnippet interface {
	GetSourceInfo() *ast.SourceInfo
}

type CycleCallback

type CycleCallback func(path []*Link, cycles int) (bool, *CycleCallbackResult)

type CycleCallbackResult

type CycleCallbackResult struct {
	// contains filtered or unexported fields
}

type DefType

type DefType string

DefType is a custom enum-like type

const (
	Function DefType = "function"
)

type Definition

type Definition struct {
	DefType DefType
	// contains filtered or unexported fields
}

type DurabilitySpec

type DurabilitySpec struct {
	RoleDurabilitySpec map[string]RoleDurabilitySpec
}

func (*DurabilitySpec) AddDurabilitySpec

func (d *DurabilitySpec) AddDurabilitySpec(evaluator *Evaluator, role *ast.Role)

func (*DurabilitySpec) HasDurabilitySpec

func (d *DurabilitySpec) HasDurabilitySpec(role string) bool

HasDurabilitySpec returns true if the role has a durability spec.

func (*DurabilitySpec) IsFieldDurable

func (d *DurabilitySpec) IsFieldDurable(role string, field string) bool

IsFieldDurable returns true if the field is durable for the role.

type Evaluator

type Evaluator struct {
	// contains filtered or unexported fields
}

func NewEvaluator

func NewEvaluator(options *syntax.FileOptions, thread *starlark.Thread) *Evaluator

func NewModelChecker

func NewModelChecker(name string) *Evaluator

func (*Evaluator) EvalExpr

func (e *Evaluator) EvalExpr(filename string, expr *ast.Expr, prevState starlark.StringDict) (starlark.Value, error)

func (*Evaluator) EvalPyExpr

func (e *Evaluator) EvalPyExpr(filename string, src interface{}, prevState starlark.StringDict) (starlark.Value, error)

func (*Evaluator) ExecAction

func (e *Evaluator) ExecAction(filename string, action *ast.Action, prevState starlark.StringDict) (bool, error)

func (*Evaluator) ExecAnyStmt

func (e *Evaluator) ExecAnyStmt(filename string, anyStmt *ast.AnyStmt, prevState starlark.StringDict) (bool, error)

func (*Evaluator) ExecBlock

func (e *Evaluator) ExecBlock(filename string, block *ast.Block, prevState starlark.StringDict) (bool, error)

func (*Evaluator) ExecForStmt

func (e *Evaluator) ExecForStmt(filename string, forStmt *ast.ForStmt, prevState starlark.StringDict) bool

func (*Evaluator) ExecIfStmt

func (e *Evaluator) ExecIfStmt(filename string, ifStmt *ast.IfStmt, prevState starlark.StringDict) bool

func (*Evaluator) ExecInit

func (e *Evaluator) ExecInit(variables *ast.StateVars) (starlark.StringDict, error)

func (*Evaluator) ExecInitOld

func (e *Evaluator) ExecInitOld(variables *ast.StateVars) (starlark.StringDict, error)

func (*Evaluator) ExecPyStmt

func (e *Evaluator) ExecPyStmt(filename string, stmt *ast.PyStmt, prevState starlark.StringDict) (bool, error)

type HashKey added in v0.2.0

type HashKey string

type Heap

type Heap struct {
	CachedHashCode string
	// contains filtered or unexported fields
}

func NewComposedHeap added in v0.2.0

func NewComposedHeap(composed map[string]*Heap) *Heap

func (*Heap) Clone

func (h *Heap) Clone(refs map[starlark.Value]starlark.Value, permutations map[lib.SymmetricValue][]lib.SymmetricValue, alt int) *Heap

func (*Heap) GetSymmetryDefs

func (h *Heap) GetSymmetryDefs() []*lib.SymmetricValues

func (*Heap) HashCode

func (h *Heap) HashCode() string

HashCode returns a string hash of the global state.

func (*Heap) MarshalJSON

func (h *Heap) MarshalJSON() ([]byte, error)

func (*Heap) String

func (h *Heap) String() string

func (*Heap) ToJson

func (h *Heap) ToJson() string

type Histogram

type Histogram struct {
	// contains filtered or unexported fields
}

func FindAbsorptionCosts

func FindAbsorptionCosts(root *Node, perfModel *proto.PerformanceModel, fileId int, invariantId int) ([]float64, *Histogram)

func (*Histogram) GetAllHistogram

func (h *Histogram) GetAllHistogram() []HistogramEntry

func (*Histogram) GetMean

func (h *Histogram) GetMean(counter string) float64

func (*Histogram) GetMeanCounts

func (h *Histogram) GetMeanCounts() map[string]float64

type HistogramEntry

type HistogramEntry struct {
	// contains filtered or unexported fields
}

type InvariantPosition

type InvariantPosition struct {
	FileIndex      int
	InvariantIndex int
}

func CheckSimpleExistsWitness

func CheckSimpleExistsWitness(nodes []*Node) []*InvariantPosition

func NewInvariantPosition

func NewInvariantPosition(fileIndex, invariantIndex int) *InvariantPosition

type JoinHashes added in v0.2.0

type JoinHashes map[HashKey][]TransitionSet
type Link struct {
	Node             *Node
	Type             string
	Name             string
	Labels           []string
	Fairness         ast.FairnessLevel
	ChoiceFairness   ast.FairnessLevel
	Messages         []*ast.Message
	ReqId            int
	ThreadsMap       map[int]int
	FailedInvariants map[int][]int
}

func AlwaysEventuallyFast

func AlwaysEventuallyFast(nodes []*Node, predicate Predicate) ([]*Link, bool)

func AlwaysEventuallyFinal

func AlwaysEventuallyFinal(nodes []*Node, root *Node, predicate Predicate) ([]*Link, bool)

func CycleFinderFinal

func CycleFinderFinal(nodes []*Node, root *Node, callback CycleCallback) ([]*Link, bool)

func CycleFinderFinalBfs

func CycleFinderFinalBfs(node *Node, callback CycleCallback) ([]*Link, bool)

func EventuallyAlwaysFast

func EventuallyAlwaysFast(nodes []*Node, predicate Predicate) ([]*Link, bool)

func EventuallyAlwaysFinal

func EventuallyAlwaysFinal(nodes []*Node, root *Node, predicate Predicate) ([]*Link, bool)

func ExtractFailurePath added in v0.2.0

func ExtractFailurePath(node *Node, rootNode *Node) []*Link
func InitNodeToLink(node *Node) *Link
func ReverseLink(node *Node, link *Link) *Link

func (*Link) HasFailedInvariants

func (l *Link) HasFailedInvariants() bool
func (l *Link) IsCrashLink() bool

type ModelError

type ModelError struct {
	SourceInfo  *proto.SourceInfo
	Msg         string
	Process     *Process
	NestedError error
}

func NewModelError

func NewModelError(sourceInfo *proto.SourceInfo, msg string, process *Process, nestedError error) *ModelError

func (*ModelError) Error

func (e *ModelError) Error() string

func (*ModelError) SprintStackTrace

func (e *ModelError) SprintStackTrace() string

type Node

type Node struct {
	*Process `json:"process"`

	Inbound  []*Link `json:"-"`
	Outbound []*Link `json:"-"`

	DuplicateOf *Node
	// contains filtered or unexported fields
}

func NewNode

func NewNode(process *Process) *Node

func (*Node) Attach

func (n *Node) Attach()

func (*Node) CreateNewToOldThreadIndexMap

func (n *Node) CreateNewToOldThreadIndexMap(other *Node) map[int]int

func (*Node) Duplicate

func (n *Node) Duplicate(other *Node, yield bool)

func (*Node) ForkForAction

func (n *Node) ForkForAction(process *Process, role *lib.Role, action *ast.Action) *Node

func (*Node) ForkForAlternatePaths

func (n *Node) ForkForAlternatePaths(process *Process, name string) *Node

func (*Node) GetJsonString

func (n *Node) GetJsonString() string

func (*Node) GetName

func (n *Node) GetName() string

GetName returns the name

func (*Node) GetStateString

func (n *Node) GetStateString() string

func (*Node) MarshalJSON

func (n *Node) MarshalJSON() ([]byte, error)

func (*Node) String

func (n *Node) String() string

String method for Process

type Predicate

type Predicate func(n *Node) (bool, bool)

type Process

type Process struct {
	Heap             *Heap         `json:"state"`
	Threads          []*Thread     `json:"threads"`
	Current          int           `json:"current"`
	Name             string        `json:"name"`
	Files            []*ast.File   `json:"-"`
	Parent           *Process      `json:"-"`
	Evaluator        *Evaluator    `json:"-"`
	Children         []*Process    `json:"-"`
	FailedInvariants map[int][]int `json:"failedInvariants"`
	Stats            *Stats        `json:"stats"`
	// Witness indicates the successful liveness checks
	// For liveness checks, not all nodes will pass the condition, witness indicates
	// which invariants this node passed.
	Witness     [][]bool               `json:"witness"`
	Returns     starlark.StringDict    `json:"returns"`
	SymbolTable map[string]*Definition `json:"-"`
	Labels      []string               `json:"-"`
	Messages    []*ast.Message         `json:"-"`

	// Fairness is actually a property of the transition/link. But to determine whether
	// the link is fair, we need to know if the process stepped through at least one
	// fair statement. To determine that, each thread maintains the fairness level
	// of the action that started. If that thread executed a statement, that process becomes fair,
	// that in-turn makes the link fair.
	Fairness ast.FairnessLevel `json:"-"`

	Enabled        bool `json:"-"`
	ThreadProgress bool `json:"-"`

	Roles    []*lib.Role          `json:"roles"`
	Channels map[int]*lib.Channel `json:"channels"`

	ChannelMessages map[int][]*ChannelMessage `json:"channel_messages"`

	CachedHashCode     string   `json:"-"`
	CachedThreadHashes []string `json:"-"`

	Modules          map[string]starlark.Value `json:"-"`
	EnableCheckpoint bool                      `json:"-"`
	ChoiceFairness   ast.FairnessLevel         `json:"-"`
	// contains filtered or unexported fields
}

func NewProcess

func NewProcess(name string, files []*ast.File, parent *Process) *Process

func (*Process) CloneForAssert

func (p *Process) CloneForAssert(permutations map[lib.SymmetricValue][]lib.SymmetricValue, alt int) *Process

func (*Process) Enable

func (p *Process) Enable()

func (*Process) Fork

func (p *Process) Fork() *Process

func (*Process) GetAllVariables

func (p *Process) GetAllVariables() starlark.StringDict

GetAllVariables returns all variables visible in the Current thread. This includes state variables and variables from the Current thread's variables in the top call frame

func (*Process) GetAllVariablesNocopy

func (p *Process) GetAllVariablesNocopy() starlark.StringDict

GetAllVariablesNocopy returns all variables visible in the Current thread, without deep copying. This includes state variables and variables from the Current thread's variables in the top call frame

func (*Process) GetSymmetryRoles

func (p *Process) GetSymmetryRoles() []*lib.SymmetricValues

func (*Process) GetThreads

func (p *Process) GetThreads() []*Thread

GetThreads returns the active threads

func (*Process) GetThreadsCount

func (p *Process) GetThreadsCount() int

func (*Process) HasFailedInvariants

func (p *Process) HasFailedInvariants() bool

func (*Process) HashCode

func (p *Process) HashCode() string

func (*Process) IsYieldNode added in v0.2.0

func (p *Process) IsYieldNode() bool

func (*Process) MarshalJSON

func (p *Process) MarshalJSON() ([]byte, error)

func (*Process) NewModelError

func (p *Process) NewModelError(sourceInfo *ast.SourceInfo, msg string, nestedError error) *ModelError

func (*Process) NewThread

func (p *Process) NewThread() *Thread

func (*Process) PanicIfFalse

func (p *Process) PanicIfFalse(ok bool, sourceInfo *ast.SourceInfo, msg string)

func (*Process) PanicOnError

func (p *Process) PanicOnError(sourceInfo *ast.SourceInfo, msg string, nestedError error)

func (*Process) RecordCall

func (p *Process) RecordCall(callerFrame *CallFrame, receiverFrame *CallFrame, flow ast.Flow)

func (*Process) RecordReturn

func (p *Process) RecordReturn(callerFrame *CallFrame, receiverFrame *CallFrame, val starlark.Value, flow ast.Flow)

type Processor

type Processor struct {
	Init  *Node
	Files []*ast.File

	Seed int64
	// contains filtered or unexported fields
}

func NewProcessor

func NewProcessor(files []*ast.File, options *ast.StateSpaceOptions, simulation bool, seed int64, dirPath string, strategy string, test bool, hashes JoinHashes) *Processor

func (*Processor) ExceedsActionCountLimits

func (p *Processor) ExceedsActionCountLimits(action *ast.Action, statProcess *Process, role *lib.Role) bool

func (*Processor) GetVisitedNodesCount

func (p *Processor) GetVisitedNodesCount() int

func (*Processor) InitializeNode

func (p *Processor) InitializeNode() (*Node, *Node, error)

func (*Processor) ResetEphemeralVariables

func (p *Processor) ResetEphemeralVariables(node *Node, oldRole *lib.Role)

func (*Processor) Start

func (p *Processor) Start() (init *Node, failedNode *Node, err error)

Start the model checker

func (*Processor) StartSimulation

func (p *Processor) StartSimulation() (init *Node, failedNode *Node, err error)

func (*Processor) Stop

func (p *Processor) Stop()

func (*Processor) Stopped

func (p *Processor) Stopped() bool

func (*Processor) YieldFork

func (p *Processor) YieldFork(node *Node, process *Process)

func (*Processor) YieldNode

func (p *Processor) YieldNode(node *Node)

type ProtoPath

type ProtoPath struct {
	// contains filtered or unexported fields
}

type RoleDurabilitySpec

type RoleDurabilitySpec struct {
	// contains filtered or unexported fields
}

type Scope

type Scope struct {
	// contains filtered or unexported fields
}

func (*Scope) GetAllVisibleVariables

func (s *Scope) GetAllVisibleVariables(roleRefs map[starlark.Value]starlark.Value) starlark.StringDict

GetAllVisibleVariables returns all variables visible in this scope.

func (*Scope) Hash

func (s *Scope) Hash() hash.Hash

func (*Scope) Lookup

func (s *Scope) Lookup(name string) (starlark.Value, bool)

func (*Scope) MarshalJSON

func (s *Scope) MarshalJSON() ([]byte, error)

func (*Scope) SetFlow

func (s *Scope) SetFlow(flow ast.Flow)

type Stats

type Stats struct {
	TotalActions int            `json:"totalActions"`
	Counts       map[string]int `json:"counts"`
}

func NewStats

func NewStats() *Stats

NewStats returns a new Stats object

func (*Stats) Clone

func (s *Stats) Clone() *Stats

func (*Stats) Increment

func (s *Stats) Increment(action string)

type Thread

type Thread struct {
	Id      int         `json:"id"`
	Process *Process    `json:"-"`
	Files   []*ast.File `json:"-"`
	Stack   *CallStack  `json:"stack"`

	Fairness ast.FairnessLevel `json:"fairness"`
	Aborted  bool              `json:"-"`
}

Thread represents a thread of execution.

func NewThread

func NewThread(Process *Process, files []*ast.File, fileIndex int, action string) *Thread

func (*Thread) Clone

func (t *Thread) Clone(permutations map[lib.SymmetricValue][]lib.SymmetricValue, alt int) *Thread

func (*Thread) CopyInitValuesForEphemeralFields

func (t *Thread) CopyInitValuesForEphemeralFields(oldFrame *CallFrame)

func (*Thread) CurrentPcSourceInfo

func (t *Thread) CurrentPcSourceInfo() *ast.SourceInfo

func (*Thread) Execute

func (t *Thread) Execute() ([]*Process, bool)

func (*Thread) ExitScope

func (t *Thread) ExitScope() *Scope

ExitScope removes the Current scope and returns the removed scope or nil if no scope was present.

func (*Thread) FindNextProgramCounter

func (t *Thread) FindNextProgramCounter() string

func (*Thread) HashCode

func (t *Thread) HashCode() string

func (*Thread) InsertNewScope

func (t *Thread) InsertNewScope() *Scope

InsertNewScope adds a new scope to the Current stack frame and returns the newly created scope.

type Transition added in v0.2.0

type Transition = lib.Pair[*Node, *Node]

type TransitionSet added in v0.2.0

type TransitionSet map[Transition]bool

type NodeSet map[*modelchecker.Node]bool

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL