unification

package
v0.0.0-...-48fa796 Latest Latest
Warning

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

 Go to latest Published: Mar 10, 2021 License: GPL-3.0 Imports: 6 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// Name is the prefix for our solver log messages.
	Name = "solver: simple"

	// ErrAmbiguous means we couldn't find a solution, but we weren't
	// inconsistent.
	ErrAmbiguous = interfaces.Error("can't unify, no equalities were consumed, we're ambiguous")

	// AllowRecursion specifies whether we're allowed to use the recursive
	// solver or not. It uses an absurd amount of memory, and might hang
	// your system if a simple solution doesn't exist.
	AllowRecursion = false

	// RecursionDepthLimit specifies the max depth that is allowed.
	// FIXME: RecursionDepthLimit is not currently implemented
	RecursionDepthLimit = 5 // TODO: pick a better value ?

	// RecursionInvariantLimit specifies the max number of invariants we can
	// recurse into.
	RecursionInvariantLimit = 5 // TODO: pick a better value ?
)

Variables

This section is empty.

Functions

func ExprListToExprMap 

func ExprListToExprMap(exprList []interfaces.Expr) map[interfaces.Expr]struct{}

ExprListToExprMap converts a list of expressions to a map that has the unique expr pointers as the keys. This is just an alternate representation of the same data structure. If you have any duplicate values in your list, they'll get removed when stored as a map.

func ExprMapToExprList 

func ExprMapToExprList(exprMap map[interfaces.Expr]struct{}) []interfaces.Expr

ExprMapToExprList converts a map of expressions to a list that has the unique expr pointers as the values. This is just an alternate representation of the same data structure.

func SimpleInvariantSolverLogger 

func SimpleInvariantSolverLogger(logf func(format string, v ...interface{})) func([]interfaces.Invariant, []interfaces.Expr) (*InvariantSolution, error)

SimpleInvariantSolverLogger is a wrapper which returns a SimpleInvariantSolver with the log parameter of your choice specified. The result satisfies the correct signature for the solver parameter of the Unification function.

func UniqueExprList 

func UniqueExprList(exprList []interfaces.Expr) []interfaces.Expr

UniqueExprList returns a unique list of expressions with no duplicates. It does this my converting it to a map and then back. This isn't necessarily the most efficient way, and doesn't preserve list ordering.

Types

type AnyInvariant 

type AnyInvariant struct {
	Expr interfaces.Expr
}

AnyInvariant is an invariant that symbolizes that the expression can be any type. It is sometimes used to ensure that an expr actually gets a solution type so that it is not left unreferenced, and as a result, unsolved. TODO: is there a better name than AnyInvariant

func (*AnyInvariant) ExprList 

func (obj *AnyInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*AnyInvariant) Matches 

func (obj *AnyInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*AnyInvariant) Possible 

func (obj *AnyInvariant) Possible([]interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation always returns nil.

func (*AnyInvariant) String 

func (obj *AnyInvariant) String() string

String returns a representation of this invariant.

type ConjunctionInvariant 

type ConjunctionInvariant struct {
	Invariants []interfaces.Invariant
}

ConjunctionInvariant represents a list of invariants which must all be true together. In other words, it's a grouping construct for a set of invariants.

func (*ConjunctionInvariant) ExprList 

func (obj *ConjunctionInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*ConjunctionInvariant) Matches 

func (obj *ConjunctionInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*ConjunctionInvariant) Possible 

func (obj *ConjunctionInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*ConjunctionInvariant) String 

func (obj *ConjunctionInvariant) String() string

String returns a representation of this invariant.

type EqualityInvariant 

type EqualityInvariant struct {
	Expr1 interfaces.Expr
	Expr2 interfaces.Expr
}

EqualityInvariant is an invariant that symbolizes that the two expressions must have equivalent types. TODO: is there a better name than EqualityInvariant

func (*EqualityInvariant) ExprList 

func (obj *EqualityInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityInvariant) Matches 

func (obj *EqualityInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityInvariant) Possible 

func (obj *EqualityInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one.

func (*EqualityInvariant) String 

func (obj *EqualityInvariant) String() string

String returns a representation of this invariant.

type EqualityInvariantList 

type EqualityInvariantList struct {
	Exprs []interfaces.Expr
}

EqualityInvariantList is an invariant that symbolizes that all the expressions listed must have equivalent types.

func (*EqualityInvariantList) ExprList 

func (obj *EqualityInvariantList) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityInvariantList) Matches 

func (obj *EqualityInvariantList) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityInvariantList) Possible 

func (obj *EqualityInvariantList) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one.

func (*EqualityInvariantList) String 

func (obj *EqualityInvariantList) String() string

String returns a representation of this invariant.

type EqualityWrapCallInvariant 

type EqualityWrapCallInvariant struct {
	Expr1     interfaces.Expr
	Expr2Func interfaces.Expr
}

EqualityWrapCallInvariant expresses that a call result that happened in Expr1 must match the type of the function result listed in Expr2. In this case, Expr2 will be a function expression, and the returned expression should match with the Expr1 expression, when comparing types. TODO: should this be named EqualityWrapFuncInvariant or not? TODO: should Expr1 and Expr2 be reversed???

func (*EqualityWrapCallInvariant) ExprList 

func (obj *EqualityWrapCallInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityWrapCallInvariant) Matches 

func (obj *EqualityWrapCallInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityWrapCallInvariant) Possible 

func (obj *EqualityWrapCallInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*EqualityWrapCallInvariant) String 

func (obj *EqualityWrapCallInvariant) String() string

String returns a representation of this invariant.

type EqualityWrapFuncInvariant 

type EqualityWrapFuncInvariant struct {
	Expr1    interfaces.Expr
	Expr2Map map[string]interfaces.Expr
	Expr2Ord []string
	Expr2Out interfaces.Expr
}

EqualityWrapFuncInvariant expresses that a func in Expr1 must have args that match the type of the expressions listed in Expr2Map and a return value that matches the type of the expression in Expr2Out. TODO: should this be named EqualityWrapCallInvariant or not?

func (*EqualityWrapFuncInvariant) ExprList 

func (obj *EqualityWrapFuncInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityWrapFuncInvariant) Matches 

func (obj *EqualityWrapFuncInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityWrapFuncInvariant) Possible 

func (obj *EqualityWrapFuncInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*EqualityWrapFuncInvariant) String 

func (obj *EqualityWrapFuncInvariant) String() string

String returns a representation of this invariant.

type EqualityWrapListInvariant 

type EqualityWrapListInvariant struct {
	Expr1    interfaces.Expr
	Expr2Val interfaces.Expr
}

EqualityWrapListInvariant expresses that a list in Expr1 must have elements that have the same type as the expression in Expr2Val.

func (*EqualityWrapListInvariant) ExprList 

func (obj *EqualityWrapListInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityWrapListInvariant) Matches 

func (obj *EqualityWrapListInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityWrapListInvariant) Possible 

func (obj *EqualityWrapListInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*EqualityWrapListInvariant) String 

func (obj *EqualityWrapListInvariant) String() string

String returns a representation of this invariant.

type EqualityWrapMapInvariant 

type EqualityWrapMapInvariant struct {
	Expr1    interfaces.Expr
	Expr2Key interfaces.Expr
	Expr2Val interfaces.Expr
}

EqualityWrapMapInvariant expresses that a map in Expr1 must have keys that match the type of the expression in Expr2Key and values that match the type of the expression in Expr2Val.

func (*EqualityWrapMapInvariant) ExprList 

func (obj *EqualityWrapMapInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityWrapMapInvariant) Matches 

func (obj *EqualityWrapMapInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityWrapMapInvariant) Possible 

func (obj *EqualityWrapMapInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*EqualityWrapMapInvariant) String 

func (obj *EqualityWrapMapInvariant) String() string

String returns a representation of this invariant.

type EqualityWrapStructInvariant 

type EqualityWrapStructInvariant struct {
	Expr1    interfaces.Expr
	Expr2Map map[string]interfaces.Expr
	Expr2Ord []string
}

EqualityWrapStructInvariant expresses that a struct in Expr1 must have fields that match the type of the expressions listed in Expr2Map.

func (*EqualityWrapStructInvariant) ExprList 

func (obj *EqualityWrapStructInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualityWrapStructInvariant) Matches 

func (obj *EqualityWrapStructInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualityWrapStructInvariant) Possible 

func (obj *EqualityWrapStructInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*EqualityWrapStructInvariant) String 

func (obj *EqualityWrapStructInvariant) String() string

String returns a representation of this invariant.

type EqualsInvariant 

type EqualsInvariant struct {
	Expr interfaces.Expr
	Type *types.Type
}

EqualsInvariant is an invariant that symbolizes that the expression has a known type. TODO: is there a better name than EqualsInvariant

func (*EqualsInvariant) ExprList 

func (obj *EqualsInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*EqualsInvariant) Matches 

func (obj *EqualsInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors.

func (*EqualsInvariant) Possible 

func (obj *EqualsInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one.

func (*EqualsInvariant) String 

func (obj *EqualsInvariant) String() string

String returns a representation of this invariant.

type ExclusiveInvariant 

type ExclusiveInvariant struct {
	Invariants []interfaces.Invariant
}

ExclusiveInvariant represents a list of invariants where one and *only* one should hold true. To combine multiple invariants in one of the list elements, you can group multiple invariants together using a ConjunctionInvariant. Do note that the solver might not verify that only one of the invariants in the list holds true, as it might choose to be lazy and pick the first solution found.

func (*ExclusiveInvariant) ExprList 

func (obj *ExclusiveInvariant) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions in this invariant.

func (*ExclusiveInvariant) Matches 

func (obj *ExclusiveInvariant) Matches(solved map[interfaces.Expr]*types.Type) (bool, error)

Matches returns whether an invariant matches the existing solution. If it is inconsistent, then it errors. Because this partial invariant requires only one to be true, it will mask children errors, since it's normal for only one to be consistent.

func (*ExclusiveInvariant) Possible 

func (obj *ExclusiveInvariant) Possible(partials []interfaces.Invariant) error

Possible returns an error if it is certain that it is NOT possible to get a solution with this invariant and the set of partials. In certain cases, it might not be able to determine that it's not possible, while simultaneously not being able to guarantee a possible solution either. In this situation, it should return nil, since this is used as a filtering mechanism, and the nil result of possible is preferred over eliminating a tricky, but possible one. This particular implementation is currently not implemented!

func (*ExclusiveInvariant) String 

func (obj *ExclusiveInvariant) String() string

String returns a representation of this invariant.

type InvariantSolution 

type InvariantSolution struct {
	Solutions []*EqualsInvariant // list of trivial solutions for each node
}

InvariantSolution lists a trivial set of EqualsInvariant mappings so that you can populate your AST with SetType calls in a simple loop.

func SimpleInvariantSolver 

func SimpleInvariantSolver(invariants []interfaces.Invariant, expected []interfaces.Expr, logf func(format string, v ...interface{})) (*InvariantSolution, error)

SimpleInvariantSolver is an iterative invariant solver for AST expressions. It is intended to be very simple, even if it's computationally inefficient.

func (*InvariantSolution) ExprList 

func (obj *InvariantSolution) ExprList() []interfaces.Expr

ExprList returns the list of valid expressions. This struct is not part of the invariant interface, but it implements this anyways.

type Unifier 

type Unifier struct {
	// AST is the input abstract syntax tree to unify.
	AST interfaces.Stmt

	// Solver is the solver algorithm implementation to use.
	Solver func([]interfaces.Invariant, []interfaces.Expr) (*InvariantSolution, error)

	Debug bool
	Logf  func(format string, v ...interface{})
}

Unifier holds all the data that the Unify function will need for it to run.

func (*Unifier) Unify 

func (obj *Unifier) Unify() error

Unify takes an AST expression tree and attempts to assign types to every node using the specified solver. The expression tree returns a list of invariants (or constraints) which must be met in order to find a unique value for the type of each expression. This list of invariants is passed into the solver, which hopefully finds a solution. If it cannot find a unique solution, then it will return an error. The invariants are available in different flavours which describe different constraint scenarios. The simplest expresses that a a particular node id (it's pointer) must be a certain type. More complicated invariants might express that two different node id's must have the same type. This function and logic was invented after the author could not find any proper literature or examples describing a well-known implementation of this process. Improvements and polite recommendations are welcome.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.