Documentation
¶
Overview ¶
Package unification contains the code related to type unification for the mcl language.
Index ¶
- Constants
- func DebugSolverState(solved map[interfaces.Expr]*types.Type, equalities []interfaces.Invariant) string
- func ExclusivesProduct(exclusives []*interfaces.ExclusiveInvariant) [][]interfaces.Invariant
- func ExprContains(needle interfaces.Expr, haystack []interfaces.Expr) bool
- func ExprListToExprMap(exprList []interfaces.Expr) map[interfaces.Expr]struct{}
- func ExprMapToExprList(exprMap map[interfaces.Expr]struct{}) []interfaces.Expr
- func Register(name string, solver func() Solver)
- func UniqueExprList(exprList []interfaces.Expr) []interfaces.Expr
- type Init
- type InvariantSolution
- type Pairs
- type Solver
- type Unifier
Constants ¶
const ( // 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") // StrategyNameKey is the string key used when choosing a solver name. StrategyNameKey = "name" // StrategyOptimizationsKey is the string key used to tell the solver // about the specific optimizations you'd like to request. The format // can be specific to each solver. StrategyOptimizationsKey = "optimizations" )
Variables ¶
This section is empty.
Functions ¶
func DebugSolverState ¶
func DebugSolverState(solved map[interfaces.Expr]*types.Type, equalities []interfaces.Invariant) string
DebugSolverState helps us in understanding the state of the type unification solver in a more mainstream format. Example:
solver state:
* str("foo") :: str * call:f(str("foo")) [0xc000ac9f10] :: ?1 * var(x) [0xc00088d840] :: ?2 * param(x) [0xc00000f950] :: ?3 * func(x) { var(x) } [0xc0000e9680] :: ?4 * ?2 = ?3 * ?4 = func(arg0 str) ?1 * ?4 = func(x str) ?2 * ?1 = ?2
func ExclusivesProduct ¶
func ExclusivesProduct(exclusives []*interfaces.ExclusiveInvariant) [][]interfaces.Invariant
ExclusivesProduct returns a list of different products produced from the combinatorial product of the list of exclusives. Each ExclusiveInvariant must contain between one and more Invariants. This takes every combination of Invariants (choosing one from each ExclusiveInvariant) and returns that list. In other words, if you have three exclusives, with invariants named (A1, B1), (A2), and (A3, B3, C3) you'll get: (A1, A2, A3), (A1, A2, B3), (A1, A2, C3), (B1, A2, A3), (B1, A2, B3), (B1, A2, C3) as results for this function call.
func ExprContains ¶
func ExprContains(needle interfaces.Expr, haystack []interfaces.Expr) bool
ExprContains is an "in array" function to test for an expr in a slice of expressions.
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 Register ¶
Register takes a solver and its name and makes it available for use. It is commonly called in the init() method of the solver at program startup. There is no matching Unregister 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 Init ¶
type Init struct {
// Strategy is a hack to tune unification performance until we have an
// overall cleaner unification algorithm in place.
Strategy map[string]string
Debug bool
Logf func(format string, v ...interface{})
}
Init contains some handles that are used to initialize every solver. Each individual solver can choose to omit using some of the fields.
type InvariantSolution ¶
type InvariantSolution struct {
Solutions []*interfaces.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 (*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 Pairs ¶
type Pairs []*interfaces.EqualityInvariant
Pairs is a simple list of pairs of expressions which can be used as a simple undirected graph structure, or as a simple list of equalities.
func (Pairs) DFS ¶
func (obj Pairs) DFS(start interfaces.Expr) []interfaces.Expr
DFS returns a depth first search for the graph, starting at the input vertex.
func (Pairs) Vertices ¶
func (obj Pairs) Vertices(expr interfaces.Expr) []interfaces.Expr
Vertices returns the list of vertices that the input expr is directly connected to.
type Solver ¶
type Solver interface {
// Init initializes the solver struct before first use.
Init(*Init) error
// Solve performs the actual solving. It must return as soon as possible
// if the context is closed.
Solve(ctx context.Context, invariants []interfaces.Invariant, expected []interfaces.Expr) (*InvariantSolution, error)
}
Solver is the general interface that any solver needs to implement.
func LookupDefault ¶
LookupDefault attempts to return a "default" solver.
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 Solver
// Strategy is a hack to tune unification performance until we have an
// overall cleaner unification algorithm in place.
Strategy map[string]string
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 ¶
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
Directories
¶
| Path | Synopsis |
|---|---|
|
Package solvers is used to have a central place to import all solvers from.
|
Package solvers is used to have a central place to import all solvers from. |