typesystem

Documentation

Overview

Package typesystem implements type-system with generics and structural subtyping. For convenience these structures have json tags (like `src` package). This is not clean architecture but it's very handy for LSP.

Index

• Variables
• type Def
  • func (def Def) String() string
• type DefaultStringer
  • func (ds DefaultStringer) String() string
• type Expr
  • func GetStructFieldTypeByPath(senderType Expr, path []string) (Expr, error)
  • func (expr *Expr) String() string
• type ExprMeta
• type Helper
  • func (h Helper) BaseDef(params ...Param) Def
  • func (h Helper) BaseDefWithRecursionAllowed(params ...Param) Def
  • func (h Helper) Def(body Expr, params ...Param) Def
  • func (h Helper) Enum(els ...string) Expr
  • func (h Helper) Inst(ref string, args ...Expr) Expr
  • func (h Helper) Param(name string, _ Expr) Param
  • func (h Helper) ParamWithNoConstr(name string) Param
  • func (h Helper) Struct(structure map[string]Expr) Expr
  • func (h Helper) Trace(ss ...string) Trace
  • func (h Helper) Union(els ...Expr) Expr
• type InstExpr
• type LitExpr
  • func (lit *LitExpr) Empty() bool
  • func (lit *LitExpr) Type() LiteralType
• type LiteralType
• type Param
• type Resolver
  • func MustNewResolver(validator exprValidator, checker subtypeChecker, ...) Resolver
  • func (r Resolver) CheckArgsCompatibility(args []Expr, params []Param, scope Scope) error
  • func (r Resolver) IsSubtypeOf(sub, sup Expr, scope Scope) error
  • func (r Resolver) ResolveExpr(expr Expr, scope Scope) (Expr, error)
  • func (r Resolver) ResolveExprWithFrame(expr Expr, frame map[string]Def, scope Scope) (Expr, error)
  • func (r Resolver) ResolveExprsWithFrame(exprs []Expr, frame map[string]Def, scope Scope) ([]Expr, error)
  • func (r Resolver) ResolveParams(params []Param, scope Scope) ([]Param, map[string]Def, error)
• type Scope
• type SubtypeChecker
  • func MustNewSubtypeChecker(terminator recursionTerminator) SubtypeChecker
  • func (s SubtypeChecker) Check(expr, constr Expr, params TerminatorParams) error
• type Terminator
  • func (r Terminator) ShouldTerminate(cur Trace, scope Scope) (bool, error)
• type TerminatorParams
• type Trace
  • func NewTrace(prev *Trace, v fmt.Stringer) Trace
  • func (t Trace) String() string
• type Validator
  • func (v Validator) CheckParamUnique(params []Param) error
  • func (v Validator) Validate(expr Expr) error
  • func (v Validator) ValidateDef(def Def) error

Variables

var (
	ErrInvalidExpr        = errors.New("expression must be valid in order to be resolved")
	ErrScope              = errors.New("can't get type def from scope by ref")
	ErrScopeUpdate        = errors.New("scope update")
	ErrInstArgsCount      = errors.New("Wrong number of type arguments")
	ErrIncompatArg        = errors.New("argument is not subtype of the parameter's contraint")
	ErrUnresolvedArg      = errors.New("can't resolve argument")
	ErrConstr             = errors.New("can't resolve constraint")
	ErrArrType            = errors.New("could not resolve array type")
	ErrUnionUnresolvedEl  = errors.New("can't resolve union element")
	ErrRecFieldUnresolved = errors.New("can't resolve struct field")
	ErrInvalidDef         = errors.New("invalid definition")
	ErrTerminator         = errors.New("recursion terminator")
)

var (
	ErrDiffKinds     = errors.New("Subtype and supertype must both be either literals or instances, except if supertype is union") //nolint:lll
	ErrDiffRefs      = errors.New("Subtype inst must have same ref as supertype")
	ErrArgsCount     = errors.New("Subtype inst must have >= args than supertype")
	ErrArgNotSubtype = errors.New("Subtype arg must be subtype of corresponding supertype arg")
	ErrLitArrSize    = errors.New("Subtype arr size must be >= supertype")
	ErrArrDiffType   = errors.New("Subtype arr must have same type as supertype")
	ErrBigEnum       = errors.New("Subtype enum must be <= supertype enum")
	ErrEnumEl        = errors.New("Subtype enum el doesn't match supertype")
	ErrStructLen     = errors.New("Subtype struct must contain >= fields than supertype")
	ErrStructField   = errors.New("Subtype struct field must be subtype of corresponding supertype field")
	ErrStructNoField = errors.New("Subtype struct is missing field of supertype")
	ErrUnion         = errors.New("Subtype must be subtype of supertype union")
	ErrUnionsLen     = errors.New("Subtype union must be <= supertype union")
	ErrUnions        = errors.New("Subtype union el must be subtype of supertype union")
	ErrDiffLitTypes  = errors.New("Subtype and supertype lits must be of the same type")
)

var (
	ErrDirectRecursion   = errors.New("type definition's body must not be directly referenced to itself")
	ErrPrevDefNotFound   = errors.New("prev def not found")
	ErrIndirectRecursion = errors.New("type definition's body must not be indirectly referenced to itself")
	ErrSwapRun           = errors.New("couldn't do test run with swapped trace")
	ErrCounter           = errors.New("recursive calls counter limit exceeded")
)

var (
	ErrExprMustBeInstOrLit = errors.New("expr must be ether literal or instantiation, not both and not neither")
	ErrUnknownLit          = errors.New("expr literal must be known")
	ErrArrSize             = errors.New("arr size must be >= 2")
	ErrArrLitKind          = errors.New("array literal must have no enum, union or struct")
	ErrUnionLitKind        = errors.New("union literal must have no enum, array or struct")
	ErrEnumLitKind         = errors.New("enum literal must have no union, array or struct")
	ErrEnumLen             = errors.New("enum len must be >= 2")
	ErrUnionLen            = errors.New("union len must be >= 2")
	ErrEnumDupl            = errors.New("enum contains duplicate elements")
	ErrParamDuplicate      = errors.New("params must have unique names")
	ErrParams              = errors.New("bad params")
)

Types

type Def

type Def struct {
	// Body can refer to these. Must be replaced with arguments while resolving
	Params []Param `json:"params,omitempty"`
	// Empty body means base type
	BodyExpr *Expr `json:"bodyExpr,omitempty"`
	// Meta can be used to store anything that can be useful for typesystem user. It is ignored by the typesystem itself.
	Meta ExprMeta `json:"meta,omitempty"`
}

func (Def) String

func (def Def) String() string

type DefaultStringer

type DefaultStringer string

func (DefaultStringer) String

func (ds DefaultStringer) String() string

type Expr

type Expr struct {
	Lit  *LitExpr  `json:"lit,omitempty"`
	Inst *InstExpr `json:"inst,omitempty"`
	Meta ExprMeta  `json:"meta,omitempty"` // This field must be ignored by the typesystem and only used outside
}

Instantiation or literal. Lit or Inst must be not nil, but not both

func GetStructFieldTypeByPath

func GetStructFieldTypeByPath(senderType Expr, path []string) (Expr, error)

func (*Expr) String

func (expr *Expr) String() string

String formats expression in a TS manner

type ExprMeta

type ExprMeta any

ExprMeta can contain any meta information that typesystem user might need e.g. source code text representation.

type Helper

type Helper struct{}

Helper is just a namespace for helper functions to avoid conflicts with entity types. It's a stateless type and it's safe to share it between goroutines.

func (Helper) BaseDef

func (h Helper) BaseDef(params ...Param) Def

Do not pass empty string as a name to avoid Body.Empty() == true

func (Helper) BaseDefWithRecursionAllowed

func (h Helper) BaseDefWithRecursionAllowed(params ...Param) Def

any base type def (without body) that has type parameters allows recursion

func (Helper) Def

func (h Helper) Def(body Expr, params ...Param) Def

func (Helper) Enum

func (h Helper) Enum(els ...string) Expr

func (Helper) Inst

func (h Helper) Inst(ref string, args ...Expr) Expr

Do not pass empty string as a name to avoid inst.Empty() == true

func (Helper) Param

func (h Helper) Param(name string, _ Expr) Param

func (Helper) ParamWithNoConstr

func (h Helper) ParamWithNoConstr(name string) Param

func (Helper) Struct

func (h Helper) Struct(structure map[string]Expr) Expr

func (Helper) Trace

func (h Helper) Trace(ss ...string) Trace

func (Helper) Union

func (h Helper) Union(els ...Expr) Expr

type InstExpr

type InstExpr struct {
	Ref  fmt.Stringer `json:"ref,omitempty"`  // Must be in the scope
	Args []Expr       `json:"args,omitempty"` // Every ref's parameter must have subtype argument
}

Instantiation expression

type LitExpr

type LitExpr struct {
	Struct map[string]Expr `json:"struct,omitempty"`
	Enum   []string        `json:"enum,omitempty"`
	Union  []Expr          `json:"union,omitempty"`
}

Literal expression. Only one field must be initialized

func (*LitExpr) Empty

func (lit *LitExpr) Empty() bool

func (*LitExpr) Type

func (lit *LitExpr) Type() LiteralType

Always call Validate before

type LiteralType

type LiteralType uint8

const (
	EmptyLitType LiteralType = iota
	ArrLitType
	StructLitType
	EnumLitType
	UnionLitType
)

type Param

type Param struct {
	Name   string `json:"name,omitempty"`   // Must be unique among other type's parameters
	Constr Expr   `json:"constr,omitempty"` // Expression that must be resolved supertype of corresponding argument
}

type Resolver

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

Resolver transforms expression it into a form where all references it contains points to resolved expressions.

func MustNewResolver

func MustNewResolver(validator exprValidator, checker subtypeChecker, terminator recursionTerminator) Resolver

func (Resolver) CheckArgsCompatibility

func (r Resolver) CheckArgsCompatibility(args []Expr, params []Param, scope Scope) error

CheckArgsCompatibility resolves args and params and then checks their compatibility.

func (Resolver) IsSubtypeOf

func (r Resolver) IsSubtypeOf(sub, sup Expr, scope Scope) error

IsSubtypeOf resolves both `sub` and `sup` expressions and returns error if `sub` is not subtype of `sup`.

func (Resolver) ResolveExpr

func (r Resolver) ResolveExpr(expr Expr, scope Scope) (Expr, error)

ResolveExpr resolves given expression using only global scope.

func (Resolver) ResolveExprWithFrame

func (r Resolver) ResolveExprWithFrame(
	expr Expr,
	frame map[string]Def,
	scope Scope,
) (
	Expr,
	error,
)

ResolveExprWithFrame works like ResolveExpr but allows to pass local scope.

func (Resolver) ResolveExprsWithFrame

func (r Resolver) ResolveExprsWithFrame(
	exprs []Expr,
	frame map[string]Def,
	scope Scope,
) (
	[]Expr,
	error,
)

ResolveExprWithFrame works like ResolveExprWithFrame but for list of expressions.

func (Resolver) ResolveParams

func (r Resolver) ResolveParams(
	params []Param,
	scope Scope,
) (
	[]Param,
	map[string]Def,
	error,
)

ResolveParams resolves every constraint in given parameter list.

type Scope

type Scope interface {
	GetType(ref fmt.Stringer) (Def, Scope, error)
	IsTopType(expr Expr) bool
}

type SubtypeChecker

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

func MustNewSubtypeChecker

func MustNewSubtypeChecker(terminator recursionTerminator) SubtypeChecker

func (SubtypeChecker) Check

func (s SubtypeChecker) Check(
	expr,
	constr Expr,
	params TerminatorParams,
) error

Check checks whether subtype is a subtype of supertype. Both subtype and supertype must be resolved. It also takes traces for those expressions and scope to handle recursive types.

type Terminator

type Terminator struct{}

func (Terminator) ShouldTerminate

func (r Terminator) ShouldTerminate(cur Trace, scope Scope) (bool, error)

type TerminatorParams

type TerminatorParams struct {
	Scope                        Scope
	SubtypeTrace, SupertypeTrace Trace
}

type Trace

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

Linked-list to handle recursive types

func NewTrace

func NewTrace(prev *Trace, v fmt.Stringer) Trace

func (Trace) String

func (t Trace) String() string

O(2n)

type Validator

type Validator struct{}

func (Validator) CheckParamUnique

func (v Validator) CheckParamUnique(params []Param) error

CheckParamUnique doesn't validate constraints, only ensures uniqueness

func (Validator) Validate

func (v Validator) Validate(expr Expr) error

Validate makes shallow validation of expr. It checks that it's inst or literal, not both and not neither; All insts are valid by default; Arr, union and enum must have size >= 2; Enum must have no duplicate elements.

func (Validator) ValidateDef

func (v Validator) ValidateDef(def Def) error

ValidateDef makes sure that type supports recursion only if it's base type and that parameters are valid