| // Copyright 2009 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package eval |
| |
| import ( |
| "bignum" |
| "go/ast" |
| "go/token" |
| "log" |
| "reflect" |
| "sort" |
| "unsafe" // For Sizeof |
| ) |
| |
| |
| // XXX(Spec) The type compatibility section is very confusing because |
| // it makes it seem like there are three distinct types of |
| // compatibility: plain compatibility, assignment compatibility, and |
| // comparison compatibility. As I understand it, there's really only |
| // assignment compatibility and comparison and conversion have some |
| // restrictions and have special meaning in some cases where the types |
| // are not otherwise assignment compatible. The comparison |
| // compatibility section is almost all about the semantics of |
| // comparison, not the type checking of it, so it would make much more |
| // sense in the comparison operators section. The compatibility and |
| // assignment compatibility sections should be rolled into one. |
| |
| type Type interface { |
| // compat returns whether this type is compatible with another |
| // type. If conv is false, this is normal compatibility, |
| // where two named types are compatible only if they are the |
| // same named type. If conv if true, this is conversion |
| // compatibility, where two named types are conversion |
| // compatible if their definitions are conversion compatible. |
| // |
| // TODO(austin) Deal with recursive types |
| compat(o Type, conv bool) bool |
| // lit returns this type's literal. If this is a named type, |
| // this is the unnamed underlying type. Otherwise, this is an |
| // identity operation. |
| lit() Type |
| // isBoolean returns true if this is a boolean type. |
| isBoolean() bool |
| // isInteger returns true if this is an integer type. |
| isInteger() bool |
| // isFloat returns true if this is a floating type. |
| isFloat() bool |
| // isIdeal returns true if this is an ideal int or float. |
| isIdeal() bool |
| // Zero returns a new zero value of this type. |
| Zero() Value |
| // String returns the string representation of this type. |
| String() string |
| // The position where this type was defined, if any. |
| Pos() token.Position |
| } |
| |
| type BoundedType interface { |
| Type |
| // minVal returns the smallest value of this type. |
| minVal() *bignum.Rational |
| // maxVal returns the largest value of this type. |
| maxVal() *bignum.Rational |
| } |
| |
| var universePos = token.Position{"<universe>", 0, 0, 0} |
| |
| /* |
| * Type array maps. These are used to memoize composite types. |
| */ |
| |
| type typeArrayMapEntry struct { |
| key []Type |
| v interface{} |
| next *typeArrayMapEntry |
| } |
| |
| type typeArrayMap map[uintptr]*typeArrayMapEntry |
| |
| func hashTypeArray(key []Type) uintptr { |
| hash := uintptr(0) |
| for _, t := range key { |
| hash = hash * 33 |
| if t == nil { |
| continue |
| } |
| addr := reflect.NewValue(t).(*reflect.PtrValue).Get() |
| hash ^= addr |
| } |
| return hash |
| } |
| |
| func newTypeArrayMap() typeArrayMap { return make(map[uintptr]*typeArrayMapEntry) } |
| |
| func (m typeArrayMap) Get(key []Type) interface{} { |
| ent, ok := m[hashTypeArray(key)] |
| if !ok { |
| return nil |
| } |
| |
| nextEnt: |
| for ; ent != nil; ent = ent.next { |
| if len(key) != len(ent.key) { |
| continue |
| } |
| for i := 0; i < len(key); i++ { |
| if key[i] != ent.key[i] { |
| continue nextEnt |
| } |
| } |
| // Found it |
| return ent.v |
| } |
| |
| return nil |
| } |
| |
| func (m typeArrayMap) Put(key []Type, v interface{}) interface{} { |
| hash := hashTypeArray(key) |
| ent, _ := m[hash] |
| |
| new := &typeArrayMapEntry{key, v, ent} |
| m[hash] = new |
| return v |
| } |
| |
| /* |
| * Common type |
| */ |
| |
| type commonType struct{} |
| |
| func (commonType) isBoolean() bool { return false } |
| |
| func (commonType) isInteger() bool { return false } |
| |
| func (commonType) isFloat() bool { return false } |
| |
| func (commonType) isIdeal() bool { return false } |
| |
| func (commonType) Pos() token.Position { return token.Position{} } |
| |
| /* |
| * Bool |
| */ |
| |
| type boolType struct { |
| commonType |
| } |
| |
| var BoolType = universe.DefineType("bool", universePos, &boolType{}) |
| |
| func (t *boolType) compat(o Type, conv bool) bool { |
| _, ok := o.lit().(*boolType) |
| return ok |
| } |
| |
| func (t *boolType) lit() Type { return t } |
| |
| func (t *boolType) isBoolean() bool { return true } |
| |
| func (boolType) String() string { |
| // Use angle brackets as a convention for printing the |
| // underlying, unnamed type. This should only show up in |
| // debug output. |
| return "<bool>" |
| } |
| |
| func (t *boolType) Zero() Value { |
| res := boolV(false) |
| return &res |
| } |
| |
| /* |
| * Uint |
| */ |
| |
| type uintType struct { |
| commonType |
| |
| // 0 for architecture-dependent types |
| Bits uint |
| // true for uintptr, false for all others |
| Ptr bool |
| name string |
| } |
| |
| var ( |
| Uint8Type = universe.DefineType("uint8", universePos, &uintType{commonType{}, 8, false, "uint8"}) |
| Uint16Type = universe.DefineType("uint16", universePos, &uintType{commonType{}, 16, false, "uint16"}) |
| Uint32Type = universe.DefineType("uint32", universePos, &uintType{commonType{}, 32, false, "uint32"}) |
| Uint64Type = universe.DefineType("uint64", universePos, &uintType{commonType{}, 64, false, "uint64"}) |
| |
| UintType = universe.DefineType("uint", universePos, &uintType{commonType{}, 0, false, "uint"}) |
| UintptrType = universe.DefineType("uintptr", universePos, &uintType{commonType{}, 0, true, "uintptr"}) |
| ) |
| |
| func (t *uintType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*uintType) |
| return ok && t == t2 |
| } |
| |
| func (t *uintType) lit() Type { return t } |
| |
| func (t *uintType) isInteger() bool { return true } |
| |
| func (t *uintType) String() string { return "<" + t.name + ">" } |
| |
| func (t *uintType) Zero() Value { |
| switch t.Bits { |
| case 0: |
| if t.Ptr { |
| res := uintptrV(0) |
| return &res |
| } else { |
| res := uintV(0) |
| return &res |
| } |
| case 8: |
| res := uint8V(0) |
| return &res |
| case 16: |
| res := uint16V(0) |
| return &res |
| case 32: |
| res := uint32V(0) |
| return &res |
| case 64: |
| res := uint64V(0) |
| return &res |
| } |
| panic("unexpected uint bit count: ", t.Bits) |
| } |
| |
| func (t *uintType) minVal() *bignum.Rational { return bignum.Rat(0, 1) } |
| |
| func (t *uintType) maxVal() *bignum.Rational { |
| bits := t.Bits |
| if bits == 0 { |
| if t.Ptr { |
| bits = uint(8 * unsafe.Sizeof(uintptr(0))) |
| } else { |
| bits = uint(8 * unsafe.Sizeof(uint(0))) |
| } |
| } |
| return bignum.MakeRat(bignum.Int(1).Shl(bits).Add(bignum.Int(-1)), bignum.Nat(1)) |
| } |
| |
| /* |
| * Int |
| */ |
| |
| type intType struct { |
| commonType |
| |
| // XXX(Spec) Numeric types: "There is also a set of |
| // architecture-independent basic numeric types whose size |
| // depends on the architecture." Should that be |
| // architecture-dependent? |
| |
| // 0 for architecture-dependent types |
| Bits uint |
| name string |
| } |
| |
| var ( |
| Int8Type = universe.DefineType("int8", universePos, &intType{commonType{}, 8, "int8"}) |
| Int16Type = universe.DefineType("int16", universePos, &intType{commonType{}, 16, "int16"}) |
| Int32Type = universe.DefineType("int32", universePos, &intType{commonType{}, 32, "int32"}) |
| Int64Type = universe.DefineType("int64", universePos, &intType{commonType{}, 64, "int64"}) |
| |
| IntType = universe.DefineType("int", universePos, &intType{commonType{}, 0, "int"}) |
| ) |
| |
| func (t *intType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*intType) |
| return ok && t == t2 |
| } |
| |
| func (t *intType) lit() Type { return t } |
| |
| func (t *intType) isInteger() bool { return true } |
| |
| func (t *intType) String() string { return "<" + t.name + ">" } |
| |
| func (t *intType) Zero() Value { |
| switch t.Bits { |
| case 8: |
| res := int8V(0) |
| return &res |
| case 16: |
| res := int16V(0) |
| return &res |
| case 32: |
| res := int32V(0) |
| return &res |
| case 64: |
| res := int64V(0) |
| return &res |
| |
| case 0: |
| res := intV(0) |
| return &res |
| } |
| panic("unexpected int bit count: ", t.Bits) |
| } |
| |
| func (t *intType) minVal() *bignum.Rational { |
| bits := t.Bits |
| if bits == 0 { |
| bits = uint(8 * unsafe.Sizeof(int(0))) |
| } |
| return bignum.MakeRat(bignum.Int(-1).Shl(bits-1), bignum.Nat(1)) |
| } |
| |
| func (t *intType) maxVal() *bignum.Rational { |
| bits := t.Bits |
| if bits == 0 { |
| bits = uint(8 * unsafe.Sizeof(int(0))) |
| } |
| return bignum.MakeRat(bignum.Int(1).Shl(bits-1).Add(bignum.Int(-1)), bignum.Nat(1)) |
| } |
| |
| /* |
| * Ideal int |
| */ |
| |
| type idealIntType struct { |
| commonType |
| } |
| |
| var IdealIntType Type = &idealIntType{} |
| |
| func (t *idealIntType) compat(o Type, conv bool) bool { |
| _, ok := o.lit().(*idealIntType) |
| return ok |
| } |
| |
| func (t *idealIntType) lit() Type { return t } |
| |
| func (t *idealIntType) isInteger() bool { return true } |
| |
| func (t *idealIntType) isIdeal() bool { return true } |
| |
| func (t *idealIntType) String() string { return "ideal integer" } |
| |
| func (t *idealIntType) Zero() Value { return &idealIntV{bignum.Int(0)} } |
| |
| /* |
| * Float |
| */ |
| |
| type floatType struct { |
| commonType |
| |
| // 0 for architecture-dependent type |
| Bits uint |
| |
| name string |
| } |
| |
| var ( |
| Float32Type = universe.DefineType("float32", universePos, &floatType{commonType{}, 32, "float32"}) |
| Float64Type = universe.DefineType("float64", universePos, &floatType{commonType{}, 64, "float64"}) |
| FloatType = universe.DefineType("float", universePos, &floatType{commonType{}, 0, "float"}) |
| ) |
| |
| func (t *floatType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*floatType) |
| return ok && t == t2 |
| } |
| |
| func (t *floatType) lit() Type { return t } |
| |
| func (t *floatType) isFloat() bool { return true } |
| |
| func (t *floatType) String() string { return "<" + t.name + ">" } |
| |
| func (t *floatType) Zero() Value { |
| switch t.Bits { |
| case 32: |
| res := float32V(0) |
| return &res |
| case 64: |
| res := float64V(0) |
| return &res |
| case 0: |
| res := floatV(0) |
| return &res |
| } |
| panic("unexpected float bit count: ", t.Bits) |
| } |
| |
| var maxFloat32Val = bignum.MakeRat(bignum.Int(0xffffff).Shl(127-23), bignum.Nat(1)) |
| var maxFloat64Val = bignum.MakeRat(bignum.Int(0x1fffffffffffff).Shl(1023-52), bignum.Nat(1)) |
| var minFloat32Val = maxFloat32Val.Neg() |
| var minFloat64Val = maxFloat64Val.Neg() |
| |
| func (t *floatType) minVal() *bignum.Rational { |
| bits := t.Bits |
| if bits == 0 { |
| bits = uint(8 * unsafe.Sizeof(float(0))) |
| } |
| switch bits { |
| case 32: |
| return minFloat32Val |
| case 64: |
| return minFloat64Val |
| } |
| log.Crashf("unexpected floating point bit count: %d", bits) |
| panic() |
| } |
| |
| func (t *floatType) maxVal() *bignum.Rational { |
| bits := t.Bits |
| if bits == 0 { |
| bits = uint(8 * unsafe.Sizeof(float(0))) |
| } |
| switch bits { |
| case 32: |
| return maxFloat32Val |
| case 64: |
| return maxFloat64Val |
| } |
| log.Crashf("unexpected floating point bit count: %d", bits) |
| panic() |
| } |
| |
| /* |
| * Ideal float |
| */ |
| |
| type idealFloatType struct { |
| commonType |
| } |
| |
| var IdealFloatType Type = &idealFloatType{} |
| |
| func (t *idealFloatType) compat(o Type, conv bool) bool { |
| _, ok := o.lit().(*idealFloatType) |
| return ok |
| } |
| |
| func (t *idealFloatType) lit() Type { return t } |
| |
| func (t *idealFloatType) isFloat() bool { return true } |
| |
| func (t *idealFloatType) isIdeal() bool { return true } |
| |
| func (t *idealFloatType) String() string { return "ideal float" } |
| |
| func (t *idealFloatType) Zero() Value { return &idealFloatV{bignum.Rat(1, 0)} } |
| |
| /* |
| * String |
| */ |
| |
| type stringType struct { |
| commonType |
| } |
| |
| var StringType = universe.DefineType("string", universePos, &stringType{}) |
| |
| func (t *stringType) compat(o Type, conv bool) bool { |
| _, ok := o.lit().(*stringType) |
| return ok |
| } |
| |
| func (t *stringType) lit() Type { return t } |
| |
| func (t *stringType) String() string { return "<string>" } |
| |
| func (t *stringType) Zero() Value { |
| res := stringV("") |
| return &res |
| } |
| |
| /* |
| * Array |
| */ |
| |
| type ArrayType struct { |
| commonType |
| Len int64 |
| Elem Type |
| } |
| |
| var arrayTypes = make(map[int64]map[Type]*ArrayType) |
| |
| // Two array types are identical if they have identical element types |
| // and the same array length. |
| |
| func NewArrayType(len int64, elem Type) *ArrayType { |
| ts, ok := arrayTypes[len] |
| if !ok { |
| ts = make(map[Type]*ArrayType) |
| arrayTypes[len] = ts |
| } |
| t, ok := ts[elem] |
| if !ok { |
| t = &ArrayType{commonType{}, len, elem} |
| ts[elem] = t |
| } |
| return t |
| } |
| |
| func (t *ArrayType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*ArrayType) |
| if !ok { |
| return false |
| } |
| return t.Len == t2.Len && t.Elem.compat(t2.Elem, conv) |
| } |
| |
| func (t *ArrayType) lit() Type { return t } |
| |
| func (t *ArrayType) String() string { return "[]" + t.Elem.String() } |
| |
| func (t *ArrayType) Zero() Value { |
| res := arrayV(make([]Value, t.Len)) |
| // TODO(austin) It's unfortunate that each element is |
| // separately heap allocated. We could add ZeroArray to |
| // everything, though that doesn't help with multidimensional |
| // arrays. Or we could do something unsafe. We'll have this |
| // same problem with structs. |
| for i := int64(0); i < t.Len; i++ { |
| res[i] = t.Elem.Zero() |
| } |
| return &res |
| } |
| |
| /* |
| * Struct |
| */ |
| |
| type StructField struct { |
| Name string |
| Type Type |
| Anonymous bool |
| } |
| |
| type StructType struct { |
| commonType |
| Elems []StructField |
| } |
| |
| var structTypes = newTypeArrayMap() |
| |
| // Two struct types are identical if they have the same sequence of |
| // fields, and if corresponding fields have the same names and |
| // identical types. Two anonymous fields are considered to have the |
| // same name. |
| |
| func NewStructType(fields []StructField) *StructType { |
| // Start by looking up just the types |
| fts := make([]Type, len(fields)) |
| for i, f := range fields { |
| fts[i] = f.Type |
| } |
| tMapI := structTypes.Get(fts) |
| if tMapI == nil { |
| tMapI = structTypes.Put(fts, make(map[string]*StructType)) |
| } |
| tMap := tMapI.(map[string]*StructType) |
| |
| // Construct key for field names |
| key := "" |
| for _, f := range fields { |
| // XXX(Spec) It's not clear if struct { T } and struct |
| // { T T } are either identical or compatible. The |
| // "Struct Types" section says that the name of that |
| // field is "T", which suggests that they are |
| // identical, but it really means that it's the name |
| // for the purpose of selector expressions and nothing |
| // else. We decided that they should be neither |
| // identical or compatible. |
| if f.Anonymous { |
| key += "!" |
| } |
| key += f.Name + " " |
| } |
| |
| // XXX(Spec) Do the tags also have to be identical for the |
| // types to be identical? I certainly hope so, because |
| // otherwise, this is the only case where two distinct type |
| // objects can represent identical types. |
| |
| t, ok := tMap[key] |
| if !ok { |
| // Create new struct type |
| t = &StructType{commonType{}, fields} |
| tMap[key] = t |
| } |
| return t |
| } |
| |
| func (t *StructType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*StructType) |
| if !ok { |
| return false |
| } |
| if len(t.Elems) != len(t2.Elems) { |
| return false |
| } |
| for i, e := range t.Elems { |
| e2 := t2.Elems[i] |
| // XXX(Spec) An anonymous and a non-anonymous field |
| // are neither identical nor compatible. |
| if e.Anonymous != e2.Anonymous || |
| (!e.Anonymous && e.Name != e2.Name) || |
| !e.Type.compat(e2.Type, conv) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| func (t *StructType) lit() Type { return t } |
| |
| func (t *StructType) String() string { |
| s := "struct {" |
| for i, f := range t.Elems { |
| if i > 0 { |
| s += "; " |
| } |
| if !f.Anonymous { |
| s += f.Name + " " |
| } |
| s += f.Type.String() |
| } |
| return s + "}" |
| } |
| |
| func (t *StructType) Zero() Value { |
| res := structV(make([]Value, len(t.Elems))) |
| for i, f := range t.Elems { |
| res[i] = f.Type.Zero() |
| } |
| return &res |
| } |
| |
| /* |
| * Pointer |
| */ |
| |
| type PtrType struct { |
| commonType |
| Elem Type |
| } |
| |
| var ptrTypes = make(map[Type]*PtrType) |
| |
| // Two pointer types are identical if they have identical base types. |
| |
| func NewPtrType(elem Type) *PtrType { |
| t, ok := ptrTypes[elem] |
| if !ok { |
| t = &PtrType{commonType{}, elem} |
| ptrTypes[elem] = t |
| } |
| return t |
| } |
| |
| func (t *PtrType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*PtrType) |
| if !ok { |
| return false |
| } |
| return t.Elem.compat(t2.Elem, conv) |
| } |
| |
| func (t *PtrType) lit() Type { return t } |
| |
| func (t *PtrType) String() string { return "*" + t.Elem.String() } |
| |
| func (t *PtrType) Zero() Value { return &ptrV{nil} } |
| |
| /* |
| * Function |
| */ |
| |
| type FuncType struct { |
| commonType |
| // TODO(austin) Separate receiver Type for methods? |
| In []Type |
| Variadic bool |
| Out []Type |
| builtin string |
| } |
| |
| var funcTypes = newTypeArrayMap() |
| var variadicFuncTypes = newTypeArrayMap() |
| |
| // Create singleton function types for magic built-in functions |
| var ( |
| capType = &FuncType{builtin: "cap"} |
| closeType = &FuncType{builtin: "close"} |
| closedType = &FuncType{builtin: "closed"} |
| lenType = &FuncType{builtin: "len"} |
| makeType = &FuncType{builtin: "make"} |
| newType = &FuncType{builtin: "new"} |
| panicType = &FuncType{builtin: "panic"} |
| paniclnType = &FuncType{builtin: "panicln"} |
| printType = &FuncType{builtin: "print"} |
| printlnType = &FuncType{builtin: "println"} |
| ) |
| |
| // Two function types are identical if they have the same number of |
| // parameters and result values and if corresponding parameter and |
| // result types are identical. All "..." parameters have identical |
| // type. Parameter and result names are not required to match. |
| |
| func NewFuncType(in []Type, variadic bool, out []Type) *FuncType { |
| inMap := funcTypes |
| if variadic { |
| inMap = variadicFuncTypes |
| } |
| |
| outMapI := inMap.Get(in) |
| if outMapI == nil { |
| outMapI = inMap.Put(in, newTypeArrayMap()) |
| } |
| outMap := outMapI.(typeArrayMap) |
| |
| tI := outMap.Get(out) |
| if tI != nil { |
| return tI.(*FuncType) |
| } |
| |
| t := &FuncType{commonType{}, in, variadic, out, ""} |
| outMap.Put(out, t) |
| return t |
| } |
| |
| func (t *FuncType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*FuncType) |
| if !ok { |
| return false |
| } |
| if len(t.In) != len(t2.In) || t.Variadic != t2.Variadic || len(t.Out) != len(t2.Out) { |
| return false |
| } |
| for i := range t.In { |
| if !t.In[i].compat(t2.In[i], conv) { |
| return false |
| } |
| } |
| for i := range t.Out { |
| if !t.Out[i].compat(t2.Out[i], conv) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| func (t *FuncType) lit() Type { return t } |
| |
| func typeListString(ts []Type, ns []*ast.Ident) string { |
| s := "" |
| for i, t := range ts { |
| if i > 0 { |
| s += ", " |
| } |
| if ns != nil && ns[i] != nil { |
| s += ns[i].Name() + " " |
| } |
| if t == nil { |
| // Some places use nil types to represent errors |
| s += "<none>" |
| } else { |
| s += t.String() |
| } |
| } |
| return s |
| } |
| |
| func (t *FuncType) String() string { |
| if t.builtin != "" { |
| return "built-in function " + t.builtin |
| } |
| args := typeListString(t.In, nil) |
| if t.Variadic { |
| if len(args) > 0 { |
| args += ", " |
| } |
| args += "..." |
| } |
| s := "func(" + args + ")" |
| if len(t.Out) > 0 { |
| s += " (" + typeListString(t.Out, nil) + ")" |
| } |
| return s |
| } |
| |
| func (t *FuncType) Zero() Value { return &funcV{nil} } |
| |
| type FuncDecl struct { |
| Type *FuncType |
| Name *ast.Ident // nil for function literals |
| // InNames will be one longer than Type.In if this function is |
| // variadic. |
| InNames []*ast.Ident |
| OutNames []*ast.Ident |
| } |
| |
| func (t *FuncDecl) String() string { |
| s := "func" |
| if t.Name != nil { |
| s += " " + t.Name.Name() |
| } |
| s += funcTypeString(t.Type, t.InNames, t.OutNames) |
| return s |
| } |
| |
| func funcTypeString(ft *FuncType, ins []*ast.Ident, outs []*ast.Ident) string { |
| s := "(" |
| s += typeListString(ft.In, ins) |
| if ft.Variadic { |
| if len(ft.In) > 0 { |
| s += ", " |
| } |
| s += "..." |
| } |
| s += ")" |
| if len(ft.Out) > 0 { |
| s += " (" + typeListString(ft.Out, outs) + ")" |
| } |
| return s |
| } |
| |
| /* |
| * Interface |
| */ |
| |
| // TODO(austin) Interface values, types, and type compilation are |
| // implemented, but none of the type checking or semantics of |
| // interfaces are. |
| |
| type InterfaceType struct { |
| commonType |
| // TODO(austin) This should be a map from names to |
| // *FuncType's. We only need the sorted list for generating |
| // the type map key. It's detrimental for everything else. |
| methods []IMethod |
| } |
| |
| type IMethod struct { |
| Name string |
| Type *FuncType |
| } |
| |
| var interfaceTypes = newTypeArrayMap() |
| |
| func NewInterfaceType(methods []IMethod, embeds []*InterfaceType) *InterfaceType { |
| // Count methods of embedded interfaces |
| nMethods := len(methods) |
| for _, e := range embeds { |
| nMethods += len(e.methods) |
| } |
| |
| // Combine methods |
| allMethods := make([]IMethod, nMethods) |
| for i, m := range methods { |
| allMethods[i] = m |
| } |
| n := len(methods) |
| for _, e := range embeds { |
| for _, m := range e.methods { |
| allMethods[n] = m |
| n++ |
| } |
| } |
| |
| // Sort methods |
| sort.Sort(iMethodSorter(allMethods)) |
| |
| mts := make([]Type, len(allMethods)) |
| for i, m := range methods { |
| mts[i] = m.Type |
| } |
| tMapI := interfaceTypes.Get(mts) |
| if tMapI == nil { |
| tMapI = interfaceTypes.Put(mts, make(map[string]*InterfaceType)) |
| } |
| tMap := tMapI.(map[string]*InterfaceType) |
| |
| key := "" |
| for _, m := range allMethods { |
| key += m.Name + " " |
| } |
| |
| t, ok := tMap[key] |
| if !ok { |
| t = &InterfaceType{commonType{}, allMethods} |
| tMap[key] = t |
| } |
| return t |
| } |
| |
| type iMethodSorter []IMethod |
| |
| func (s iMethodSorter) Less(a, b int) bool { return s[a].Name < s[b].Name } |
| |
| func (s iMethodSorter) Swap(a, b int) { s[a], s[b] = s[b], s[a] } |
| |
| func (s iMethodSorter) Len() int { return len(s) } |
| |
| func (t *InterfaceType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*InterfaceType) |
| if !ok { |
| return false |
| } |
| if len(t.methods) != len(t2.methods) { |
| return false |
| } |
| for i, e := range t.methods { |
| e2 := t2.methods[i] |
| if e.Name != e2.Name || !e.Type.compat(e2.Type, conv) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| func (t *InterfaceType) lit() Type { return t } |
| |
| func (t *InterfaceType) String() string { |
| // TODO(austin) Instead of showing embedded interfaces, this |
| // shows their methods. |
| s := "interface {" |
| for i, m := range t.methods { |
| if i > 0 { |
| s += "; " |
| } |
| s += m.Name + funcTypeString(m.Type, nil, nil) |
| } |
| return s + "}" |
| } |
| |
| // implementedBy tests if o implements t, returning nil, true if it does. |
| // Otherwise, it returns a method of t that o is missing and false. |
| func (t *InterfaceType) implementedBy(o Type) (*IMethod, bool) { |
| if len(t.methods) == 0 { |
| return nil, true |
| } |
| |
| // The methods of a named interface types are those of the |
| // underlying type. |
| if it, ok := o.lit().(*InterfaceType); ok { |
| o = it |
| } |
| |
| // XXX(Spec) Interface types: "A type implements any interface |
| // comprising any subset of its methods" It's unclear if |
| // methods must have identical or compatible types. 6g |
| // requires identical types. |
| |
| switch o := o.(type) { |
| case *NamedType: |
| for _, tm := range t.methods { |
| sm, ok := o.methods[tm.Name] |
| if !ok || sm.decl.Type != tm.Type { |
| return &tm, false |
| } |
| } |
| return nil, true |
| |
| case *InterfaceType: |
| var ti, oi int |
| for ti < len(t.methods) && oi < len(o.methods) { |
| tm, om := &t.methods[ti], &o.methods[oi] |
| switch { |
| case tm.Name == om.Name: |
| if tm.Type != om.Type { |
| return tm, false |
| } |
| ti++ |
| oi++ |
| case tm.Name > om.Name: |
| oi++ |
| default: |
| return tm, false |
| } |
| } |
| if ti < len(t.methods) { |
| return &t.methods[ti], false |
| } |
| return nil, true |
| } |
| |
| return &t.methods[0], false |
| } |
| |
| func (t *InterfaceType) Zero() Value { return &interfaceV{} } |
| |
| /* |
| * Slice |
| */ |
| |
| type SliceType struct { |
| commonType |
| Elem Type |
| } |
| |
| var sliceTypes = make(map[Type]*SliceType) |
| |
| // Two slice types are identical if they have identical element types. |
| |
| func NewSliceType(elem Type) *SliceType { |
| t, ok := sliceTypes[elem] |
| if !ok { |
| t = &SliceType{commonType{}, elem} |
| sliceTypes[elem] = t |
| } |
| return t |
| } |
| |
| func (t *SliceType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*SliceType) |
| if !ok { |
| return false |
| } |
| return t.Elem.compat(t2.Elem, conv) |
| } |
| |
| func (t *SliceType) lit() Type { return t } |
| |
| func (t *SliceType) String() string { return "[]" + t.Elem.String() } |
| |
| func (t *SliceType) Zero() Value { |
| // The value of an uninitialized slice is nil. The length and |
| // capacity of a nil slice are 0. |
| return &sliceV{Slice{nil, 0, 0}} |
| } |
| |
| /* |
| * Map type |
| */ |
| |
| type MapType struct { |
| commonType |
| Key Type |
| Elem Type |
| } |
| |
| var mapTypes = make(map[Type]map[Type]*MapType) |
| |
| func NewMapType(key Type, elem Type) *MapType { |
| ts, ok := mapTypes[key] |
| if !ok { |
| ts = make(map[Type]*MapType) |
| mapTypes[key] = ts |
| } |
| t, ok := ts[elem] |
| if !ok { |
| t = &MapType{commonType{}, key, elem} |
| ts[elem] = t |
| } |
| return t |
| } |
| |
| func (t *MapType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*MapType) |
| if !ok { |
| return false |
| } |
| return t.Elem.compat(t2.Elem, conv) && t.Key.compat(t2.Key, conv) |
| } |
| |
| func (t *MapType) lit() Type { return t } |
| |
| func (t *MapType) String() string { return "map[" + t.Key.String() + "] " + t.Elem.String() } |
| |
| func (t *MapType) Zero() Value { |
| // The value of an uninitialized map is nil. |
| return &mapV{nil} |
| } |
| |
| /* |
| type ChanType struct { |
| // TODO(austin) |
| } |
| */ |
| |
| /* |
| * Named types |
| */ |
| |
| type Method struct { |
| decl *FuncDecl |
| fn Func |
| } |
| |
| type NamedType struct { |
| token.Position |
| Name string |
| // Underlying type. If incomplete is true, this will be nil. |
| // If incomplete is false and this is still nil, then this is |
| // a placeholder type representing an error. |
| Def Type |
| // True while this type is being defined. |
| incomplete bool |
| methods map[string]Method |
| } |
| |
| // TODO(austin) This is temporarily needed by the debugger's remote |
| // type parser. This should only be possible with block.DefineType. |
| func NewNamedType(name string) *NamedType { |
| return &NamedType{token.Position{}, name, nil, true, make(map[string]Method)} |
| } |
| |
| func (t *NamedType) Complete(def Type) { |
| if !t.incomplete { |
| log.Crashf("cannot complete already completed NamedType %+v", *t) |
| } |
| // We strip the name from def because multiple levels of |
| // naming are useless. |
| if ndef, ok := def.(*NamedType); ok { |
| def = ndef.Def |
| } |
| t.Def = def |
| t.incomplete = false |
| } |
| |
| func (t *NamedType) compat(o Type, conv bool) bool { |
| t2, ok := o.(*NamedType) |
| if ok { |
| if conv { |
| // Two named types are conversion compatible |
| // if their literals are conversion |
| // compatible. |
| return t.Def.compat(t2.Def, conv) |
| } else { |
| // Two named types are compatible if their |
| // type names originate in the same type |
| // declaration. |
| return t == t2 |
| } |
| } |
| // A named and an unnamed type are compatible if the |
| // respective type literals are compatible. |
| return o.compat(t.Def, conv) |
| } |
| |
| func (t *NamedType) lit() Type { return t.Def.lit() } |
| |
| func (t *NamedType) isBoolean() bool { return t.Def.isBoolean() } |
| |
| func (t *NamedType) isInteger() bool { return t.Def.isInteger() } |
| |
| func (t *NamedType) isFloat() bool { return t.Def.isFloat() } |
| |
| func (t *NamedType) isIdeal() bool { return false } |
| |
| func (t *NamedType) String() string { return t.Name } |
| |
| func (t *NamedType) Zero() Value { return t.Def.Zero() } |
| |
| /* |
| * Multi-valued type |
| */ |
| |
| // MultiType is a special type used for multi-valued expressions, akin |
| // to a tuple type. It's not generally accessible within the |
| // language. |
| type MultiType struct { |
| commonType |
| Elems []Type |
| } |
| |
| var multiTypes = newTypeArrayMap() |
| |
| func NewMultiType(elems []Type) *MultiType { |
| if t := multiTypes.Get(elems); t != nil { |
| return t.(*MultiType) |
| } |
| |
| t := &MultiType{commonType{}, elems} |
| multiTypes.Put(elems, t) |
| return t |
| } |
| |
| func (t *MultiType) compat(o Type, conv bool) bool { |
| t2, ok := o.lit().(*MultiType) |
| if !ok { |
| return false |
| } |
| if len(t.Elems) != len(t2.Elems) { |
| return false |
| } |
| for i := range t.Elems { |
| if !t.Elems[i].compat(t2.Elems[i], conv) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| var EmptyType Type = NewMultiType([]Type{}) |
| |
| func (t *MultiType) lit() Type { return t } |
| |
| func (t *MultiType) String() string { |
| if len(t.Elems) == 0 { |
| return "<none>" |
| } |
| return typeListString(t.Elems, nil) |
| } |
| |
| func (t *MultiType) Zero() Value { |
| res := make([]Value, len(t.Elems)) |
| for i, t := range t.Elems { |
| res[i] = t.Zero() |
| } |
| return multiV(res) |
| } |
| |
| /* |
| * Initialize the universe |
| */ |
| |
| func init() { |
| // To avoid portability issues all numeric types are distinct |
| // except byte, which is an alias for uint8. |
| |
| // Make byte an alias for the named type uint8. Type aliases |
| // are otherwise impossible in Go, so just hack it here. |
| universe.defs["byte"] = universe.defs["uint8"] |
| |
| // Built-in functions |
| universe.DefineConst("cap", universePos, capType, nil) |
| universe.DefineConst("close", universePos, closeType, nil) |
| universe.DefineConst("closed", universePos, closedType, nil) |
| universe.DefineConst("len", universePos, lenType, nil) |
| universe.DefineConst("make", universePos, makeType, nil) |
| universe.DefineConst("new", universePos, newType, nil) |
| universe.DefineConst("panic", universePos, panicType, nil) |
| universe.DefineConst("panicln", universePos, paniclnType, nil) |
| universe.DefineConst("print", universePos, printType, nil) |
| universe.DefineConst("println", universePos, printlnType, nil) |
| } |