types

package
v0.0.0-...-90deddd Latest Latest
Warning

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

 Go to latest Published: Oct 18, 2023 License: Apache-2.0 Imports: 7 Imported by: 6

Documentation

Overview

Package types contains data structures and algorithms for dealing with value types in Reflow. In particular, it defines type-trees, constructors for type trees, together with unification and subtyping algorithms.

A Reflow type is one of: 

bottom                                    the type of no values
top                                       the type of any value
int                                       the type of arbitrary precision integers
float                                     the type of arbitrary precision float point numbers
string                                    the type of (utf-8 encoded) strings
bool                                      the type of booleans
file                                      the type of files
dir                                       the type of directories
unit                                      the type of single-valued unit/void
fileset                                   the type of filesets (legacy)
<ident>                                   a type reference to ident
[t]                                       the type of lists of element type t
[t1:t2]                                   the type of maps of index type t1, element type t2
(t1, t2, ..., tn)                         the type of tuples of type t1, ..., tn
func(arg1 t1, arg2 t2, ..., argn tn) t    the type of function with arguments t1, ..., tn, and return type t
{k1: t1, k2: t2, ..., kn: tn}             the type of struct with fields k1, ..., kn, of types t1, ..., tn
module{I1: t1, I2: t2, ..., In: tn,
       type a1 at1, type a2 at2}          the type of module with values I1, ... In, of types t1, ..., tn
                                          and type aliases a1, a2 of at1, at2.
#{Tag1(t1) | Tag2(t2) | ... | TagN(tn)}   the type of sum types with tagged variants Tag1, Tag2, ..., TagN

See package grail.com/reflow/syntax for parsing concrete syntax into type trees.

Each type carries a const level: NotConst, CanConst, or Const. Level Const indicates that values of this type do not depend on dynamic program input, and can be computed constantly within a simple module-level lexical scope. CanConst types may be upgraded to Const by static analysis, whereas NotConst types may never be Const. Unification imposes a maximum const level, and a type's constedness is affirmed by T.Const. This API requires the static analyzer to explicitly propagate const levels.

Types of level Const may also carry a set of predicates, indicating that their constedness is conditional. The static analyzer can mint fresh predicates (for example indicating that a module's parameter is satisfied by a constant type), and then later derive types based on satisfied predicates. This is used to implement cross-module constant propagation within Reflow.

Two types are unified by recursively computing the common subtype of the two arguments. Subtyping is limited to structs and modules; type equality is required for all other types.

Index

Constants

This section is empty.

Variables

View Source 
var (
	Bottom  = &T{Kind: BottomKind}
	Top     = &T{Kind: TopKind}
	Int     = &T{Kind: IntKind}
	Float   = &T{Kind: FloatKind}
	String  = &T{Kind: StringKind}
	Bool    = &T{Kind: BoolKind}
	File    = &T{Kind: FileKind}
	Dir     = &T{Kind: DirKind, Elem: Tuple(&Field{T: String}, &Field{T: File})}
	Unit    = &T{Kind: UnitKind}
	Fileset = &T{Kind: FilesetKind}
)

Convenience vars for common types.

Functions

func FieldsString 

func FieldsString(fields []*Field) string

FieldsString returns a parseable string representation of the given fields.

func IsExported 

func IsExported(ident string) bool

IsExported returns whether the provided identifier is considered exported: that is, it begins in an uppercase character as defined by unicode.

Types

type ConstLevel 

type ConstLevel int

ConstLevel determines the "constedness" of a type. See definitions below. 

const (
	// NotConst indicates that the value represented by this type
	// cannot be computed statically by the compiler.
	NotConst ConstLevel = -1
	// CanConst indicates that the value represented by this type is
	// derived from IsConst values, and thus may be promoted to
	// IsConst if the underlying operation allows for it.
	CanConst ConstLevel = 0
	// Const indicates that the value represented by this type can
	// be computed statically by the compiler.
	Const ConstLevel = 1
)

func (ConstLevel) Min 

func (l ConstLevel) Min(m ConstLevel) ConstLevel

Min returns the smaller (more conservative) of m and l.

func (ConstLevel) String 

func (i ConstLevel) String() string

type Env 

type Env struct {
	Values, Types Symtab
	// contains filtered or unexported fields
}

Env represents a type environment that binds value and type identifiers to *Ts.

func NewEnv 

func NewEnv() *Env

NewEnv creates and initializes a new Env.

func (*Env) Alias 

func (e *Env) Alias(id string) *T

Alias returns the type alias bound to identifier id, if any.

func (*Env) Bind 

func (e *Env) Bind(id string, t *T, pos scanner.Position, use Use)

Bind binds the identifier id to type t.

func (*Env) BindAlias 

func (e *Env) BindAlias(id string, t *T)

BindAlias binds the type t to the type alias with the provided identifier.

func (*Env) Pop 

func (e *Env) Pop() *Env

Pop returns the topmost frame in env. The returned frame is unlinked.

func (*Env) Push 

func (e *Env) Push() *Env

Push returns a new environment level linked to e.

func (*Env) Symbols 

func (e *Env) Symbols() map[string]*T

Symbols returns the full value environment as a map.

func (*Env) Type 

func (e *Env) Type(id string) *T

Type returns the type bound to identifier id, if any.

func (*Env) Unused 

func (e *Env) Unused() []*Symbol

Unused returns the set of symbols that are currently considered unused according to the use rules provided at the time of binding.

func (*Env) Use 

func (e *Env) Use(id string)

Use marks the provided identifier as used.

type Field 

type Field struct {
	Name string
	*T
}

A Field is a labelled type. It is used in records, function arguments, and tuples.

func (*Field) Equal 

func (f *Field) Equal(e *Field) bool

Equal checks whether Field f is equivalent to Field e.

func (*Field) String 

func (f *Field) String() string

type Kind 

type Kind int

Kind represents a type's kind. 

const (
	// ErrorKind is an illegal type.
	ErrorKind Kind = iota

	// BottomKind is a value-less type.
	BottomKind

	// TopKind is the type of any value.
	TopKind

	// IntKind is the type of arbitrary precision integers.
	IntKind
	// FloatKind is the type of arbitrary precision floats.
	FloatKind
	// StringKind is the type of UTF-8 encoded strings.
	StringKind
	// BoolKind is the type of booleans.
	BoolKind
	// FileKind is the type of files.
	FileKind
	// DirKind is the type of directories.
	DirKind
	// FilesetKind is the type of filesets.
	FilesetKind
	// UnitKind is a 1-valued type.
	UnitKind

	// ListKind is the type of lists.
	ListKind
	// MapKind is the type of maps.
	MapKind

	// TupleKind is the kind of n-tuples of values (containing positional fields).
	TupleKind
	// FuncKind is the type of funcs (arguments and return types).
	FuncKind
	// StructKind is the type of structs (containing named fields).
	StructKind

	// ModuleKind is the type of modules. They are like structs,
	// but: (1) will eventually also contain types; (2) can never
	// be subject to delayed evaluation: their values are known
	// at compile time.
	ModuleKind

	// SumKind is the kind of sum types. Note that sum types are polymorphic,
	// e.g. #Int(int) | #String(string) is a subtype of #Int(int) |
	// #String(string) | #Float(float).
	SumKind

	// RefKind is a pseudo-kind to carry type alias references.
	RefKind
)

func (Kind) ID 

func (k Kind) ID() byte

ID returns the kind's stable identifier, which may be used for serialization.

func (Kind) String 

func (k Kind) String() string

type Predicate 

type Predicate int

A Predicate represents a condition upon which a type's constedness is predictated.

func FreshPredicate 

func FreshPredicate() Predicate

FreshPredicate returns a fresh predicate.

type Predicates 

type Predicates map[Predicate]bool

Predicates is a predicate set.

func (*Predicates) Add 

func (p *Predicates) Add(pred Predicate)

Add adds predicate pred to the predicate set.

func (*Predicates) AddAll 

func (p *Predicates) AddAll(q Predicates)

AddAll adds all predicates in q to p.

func (*Predicates) Clear 

func (p *Predicates) Clear()

Clear removes all predicates from the set.

func (Predicates) Copy 

func (p Predicates) Copy() Predicates

Copy returns a copy of the the predicate set p.

func (Predicates) NIntersect 

func (p Predicates) NIntersect(q Predicates) int

NIntersect returns the number of predicates shared by predicate sets p and q.

func (Predicates) RemoveAll 

func (p Predicates) RemoveAll(q Predicates)

RemoveAll removes from set p all predicates in q.

func (Predicates) Satisfies 

func (p Predicates) Satisfies(q Predicates) bool

Satisfies determines whether the predicate set p meets the predicate set q: that is, whether all predicates in q are present in p.

type Symbol 

type Symbol struct {
	// Position is the scanner position of the symbol; used
	// for error reporting.
	scanner.Position
	// Name is the identifier of the symbol.
	Name string
	// Value is the type of the symbol.
	Value *T
	// Use is the use rule of the symbol.
	Use Use
	// Used is true if the binding has been marked used.
	Used bool
}

Symbol stores symbol information for a binding maintained by an environment.

type Symtab 

type Symtab map[string]*Symbol

Symtab is a symbol table of symbols.

type T 

type T struct {
	// Kind is the kind of the type. See above.
	Kind Kind
	// Index is the type of the type's index; used in maps.
	Index *T
	// Elem is the type of the type's elem; used in lists, maps, dirs, and funcs.
	Elem *T
	// Fields stores module, struct, and tuple fields, as well as func
	// arguments.
	Fields []*Field
	// Aliases stores a module's (exported) type aliases.
	Aliases []*Field
	// Error holds the type's error.
	Error error

	// Variants holds the variants of this type; used in sum types.
	Variants []*Variant

	// Path is a type reference path, used by RefKind.
	// It is also used after alias expansion to retain identifiers
	// for pretty printing.
	Path []string

	// Label is an optional label for this type.
	// It does not affect the type's semantics.
	Label string

	// Flow is a flag indicating that types of this value are derived
	// from *flow.Flow evaluations. This is used in the type checker
	// to check for "immediate" evaluation.
	Flow bool

	// Level is this type's const level.
	Level ConstLevel
	// Predicates is the set of predicates upon which the types
	// constedness is predicated.
	Predicates Predicates
}

A T is a Reflow type. The zero T is a TypeError.

func Error 

func Error(err error) *T

Error constructs a new error type.

func Errorf 

func Errorf(format string, args ...interface{}) *T

Errorf formats a new error type

func Flow 

func Flow(t *T) *T

Flow returns type t as a flow type.

func Func 

func Func(elem *T, fields ...*Field) *T

Func returns a new func type with the given element (return type) and argument fields.

func Labeled 

func Labeled(label string, t *T) *T

Labeled returns a labeled version of type t.

func List 

func List(elem *T) *T

List returns a new list type with the given element type.

func Make 

func Make(t *T) *T

Make initializes type t and returns it, propagating errors of any child type.

func Map 

func Map(index, elem *T) *T

Map returns a new map type with the given index and element types.

func Module 

func Module(fields []*Field, aliases []*Field) *T

Module returns a new module type with the given fields.

func Ref 

func Ref(path ...string) *T

Ref returns a new pseudo-type reference to the given path.

func Struct 

func Struct(fields ...*Field) *T

Struct returns a new struct type with the given fields.

func Sum 

func Sum(variants ...*Variant) *T

Sum returns a new sum type with the given variants. Tags must be unique. Tags must begin with uppercase. There must be at least one variant.

func Swizzle 

func Swizzle(t *T, maxlevel ConstLevel, ts ...*T) *T

Swizzle returns a version of t with modified const and flow flags:

  • if any of the type ts are NotConst, the returned type is also NotConst
  • const predicates from type ts are added to t's predicate set
  • t's flow flag is set if any of type ts are
  • the returned type's level is at most maxlevel

func Tuple 

func Tuple(fields ...*Field) *T

Tuple returns a new tuple type with the given fields.

func Unify 

func Unify(maxlevel ConstLevel, ts ...*T) *T

Unify returns the minimal common supertype of ts. That is, where u := Unify(ts), then forall t in ts. t <: u, and there exists no v, v != u and v <: u, such that forall t in ts. t <: v. Unify returns an error type if unification is impossible. The returned type's const level is limited by the provided maxlevel.

func (*T) Alias 

func (t *T) Alias(id string) *T

Alias returns the alias id in a module type, if any.

func (*T) Const 

func (t *T) Const(predicates ...Predicate) *T

Const affirms type t's constedness with an additional set of predicates. The returned type is const only if all child types are also const.

func (*T) Copy 

func (t *T) Copy() *T

Copy returns a shallow copy of type t.

func (*T) Equal 

func (t *T) Equal(u *T) bool

Equal tests whether type t is equivalent to type u.

func (*T) Field 

func (t *T) Field(n string) *T

Field indexes the type's fields.

func (*T) FieldMap 

func (t *T) FieldMap() map[string]*T

FieldMap returns the Type's fields as a map.

func (*T) Ident 

func (t *T) Ident() string

Ident returns the identifier of this type (the expanded path).

func (*T) IsConst 

func (t *T) IsConst(predicates Predicates) bool

IsConst tells whether type t is const given the provided predicates.

func (*T) Map 

func (t *T) Map(fn func(*T) *T) *T

Map applies fn structurally in a depth-first fashion. If fn performs modifications to type t, it should return a copy.

func (*T) NotConst 

func (t *T) NotConst() *T

NotConst denies constedness to type t. NotConst is tainting: all child types are marked NotConst as well. Thus NotConst can be used in static analysis where non-const dataflow is introduced.

func (*T) Satisfied 

func (t *T) Satisfied(predicates Predicates) *T

Satisfied returns type t with the given predicates satisfied.

func (*T) String 

func (t *T) String() string

String renders a parseable version of Type t.

func (*T) StructurallyEqual 

func (t *T) StructurallyEqual(u *T) bool

StructurallyEqual tells whether type t is structurally equal to type u. Structural equality permits type aliases and considers two aliases equal if their paths are equal.

func (*T) Sub 

func (t *T) Sub(u *T) bool

Sub tells whether t is a subtype of u. Subtyping is only applied to structs and modules, as in (*T).Unify.

func (*T) Tupled 

func (t *T) Tupled() *T

Tupled returns a tuple version of this type's fields.

func (*T) VariantMap 

func (t *T) VariantMap() map[string]*T

VariantMap returns the Type's variant elements as a map, keyed by tag.

type Use 

type Use int

Use denotes how a binding is consider used. 

const (
	// Always indicates that a binding is always unused unless
	// explicitly marked used.
	Always Use = iota
	// Never indicates that a binding is never considered unused.
	Never
	// Unexported denotes that a binding is considered unused
	// only if it is unexported.
	Unexported
)

type Variant 

type Variant struct {
	// Tag is the unique identifier of the variant within the type.
	Tag string
	// Elem is the type of this variant.  It may be nil, in which case the
	// variant is just the tag.
	Elem *T
}

Variant represents a single variant of a sum type.

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.