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 ArrLit
• 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) Arr(size int, typ Expr) Expr
  • 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, constr 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) 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) ResolveFrame(args []Expr, params []Param, scope Scope) ([]Expr, map[string]Def, error)
  • func (r Resolver) ResolveParams(params []Param, scope Scope) ([]Param, 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")
	ErrInstArgsLen        = errors.New("inst must have same number of arguments as def has parameters")
	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 record 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")
	ErrRecLen        = errors.New("Subtype record must contain >= fields than supertype")
	ErrRecField      = errors.New("Subtype rec field must be subtype of corresponding supertype field")
	ErrRecNoField    = errors.New("Subtype rec 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 record")
	ErrUnionLitKind                 = errors.New("union literal must have no enum, array or record")
	ErrEnumLitKind                  = errors.New("enum literal must have no union, array or record")
	ErrEnumLen                      = errors.New("enum len must be >= 2")
	ErrUnionLen                     = errors.New("union len must be >= 2")
	ErrEnumDupl                     = errors.New("enum contains duplicate elements")
	ErrNotBaseTypeSupportsRecursion = errors.New("only base type definitions can have support for recursion")
	ErrParamDuplicate               = errors.New("params must have unique names")
	ErrParams                       = errors.New("bad params")
)

Types

type ArrLit

type ArrLit struct {
	Expr Expr `json:"expr,omitempty"`
	Size int  `json:"size,omitempty"`
}

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"`
	// Only base types can have true.
	CanBeUsedForRecursiveDefinitions bool `json:"canBeUsedForRecursiveDefinitions,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) Arr

func (h Helper) Arr(size int, typ Expr) Expr

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

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, constr 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 {
	Arr    *ArrLit         `json:"arr,omitempty"`
	Struct map[string]Expr `json:"rec,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
	RecLitType
	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) IsSubtypeOf

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

func (Resolver) ResolveExpr

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

func (Resolver) ResolveExprWithFrame

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

func (Resolver) ResolveFrame

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

ResolveFrame resolves arguments and parameters and checks that they are compatible. If everything is okay it returns resolved args and resulting frame. It's copy-paste from resolveExpr method because it's hard to reuse that code without creating useless expr and scope.

func (Resolver) ResolveParams

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

Note that it has no sense to "resolve definition". You can resolve only type parameters (their constraints). This is because def's body, type expr, must be resolved only at instantiation (argument passing) step. Otherwise simply break substitution by replacing param refs with constraints expressions.

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