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 ¶
- Variables
- func FieldsString(fields []*Field) string
- func IsExported(ident string) bool
- type ConstLevel
- type Env
- func (e *Env) Alias(id string) *T
- func (e *Env) Bind(id string, t *T, pos scanner.Position, use Use)
- func (e *Env) BindAlias(id string, t *T)
- func (e *Env) Pop() *Env
- func (e *Env) Push() *Env
- func (e *Env) Symbols() map[string]*T
- func (e *Env) Type(id string) *T
- func (e *Env) Unused() []*Symbol
- func (e *Env) Use(id string)
- type Field
- type Kind
- type Predicate
- type Predicates
- type Symbol
- type Symtab
- type T
- func Error(err error) *T
- func Errorf(format string, args ...interface{}) *T
- func Flow(t *T) *T
- func Func(elem *T, fields ...*Field) *T
- func Labeled(label string, t *T) *T
- func List(elem *T) *T
- func Make(t *T) *T
- func Map(index, elem *T) *T
- func Module(fields []*Field, aliases []*Field) *T
- func Ref(path ...string) *T
- func Struct(fields ...*Field) *T
- func Sum(variants ...*Variant) *T
- func Swizzle(t *T, maxlevel ConstLevel, ts ...*T) *T
- func Tuple(fields ...*Field) *T
- func Unify(maxlevel ConstLevel, ts ...*T) *T
- func (t *T) Alias(id string) *T
- func (t *T) Const(predicates ...Predicate) *T
- func (t *T) Copy() *T
- func (t *T) Equal(u *T) bool
- func (t *T) Field(n string) *T
- func (t *T) FieldMap() map[string]*T
- func (t *T) Ident() string
- func (t *T) IsConst(predicates Predicates) bool
- func (t *T) Map(fn func(*T) *T) *T
- func (t *T) NotConst() *T
- func (t *T) Satisfied(predicates Predicates) *T
- func (t *T) String() string
- func (t *T) StructurallyEqual(u *T) bool
- func (t *T) Sub(u *T) bool
- func (t *T) Tupled() *T
- func (t *T) VariantMap() map[string]*T
- type Use
- type Variant
Constants ¶
This section is empty.
Variables ¶
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 ¶
FieldsString returns a parseable string representation of the given fields.
func IsExported ¶
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.
type Field ¶
A Field is a labelled type. It is used in records, function arguments, and tuples.
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 )
type Predicate ¶
type Predicate int
A Predicate represents a condition upon which a type's constedness is predictated.
type Predicates ¶
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) 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 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 Sum ¶
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 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) Const ¶
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) IsConst ¶
func (t *T) IsConst(predicates Predicates) bool
IsConst tells whether type t is const given the provided predicates.
func (*T) Map ¶
Map applies fn structurally in a depth-first fashion. If fn performs modifications to type t, it should return a copy.
func (*T) NotConst ¶
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) StructurallyEqual ¶
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 ¶
Sub tells whether t is a subtype of u. Subtyping is only applied to structs and modules, as in (*T).Unify.
func (*T) VariantMap ¶
VariantMap returns the Type's variant elements as a map, keyed by tag.
Source Files