libgo/go/exp/eval/type.go

   1 // Copyright 2009 The Go Authors.  All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package eval
   6
   7 import (
   8         "big"
   9         "go/ast"
  10         "go/token"
  11         "log"
  12         "reflect"
  13         "sort"
  14         "unsafe" // For Sizeof
  15 )
  16
  17
  18 // XXX(Spec) The type compatibility section is very confusing because
  19 // it makes it seem like there are three distinct types of
  20 // compatibility: plain compatibility, assignment compatibility, and
  21 // comparison compatibility.  As I understand it, there's really only
  22 // assignment compatibility and comparison and conversion have some
  23 // restrictions and have special meaning in some cases where the types
  24 // are not otherwise assignment compatible.  The comparison
  25 // compatibility section is almost all about the semantics of
  26 // comparison, not the type checking of it, so it would make much more
  27 // sense in the comparison operators section.  The compatibility and
  28 // assignment compatibility sections should be rolled into one.
  29
  30 type Type interface {
  31         // compat returns whether this type is compatible with another
  32         // type.  If conv is false, this is normal compatibility,
  33         // where two named types are compatible only if they are the
  34         // same named type.  If conv if true, this is conversion
  35         // compatibility, where two named types are conversion
  36         // compatible if their definitions are conversion compatible.
  37         //
  38         // TODO(austin) Deal with recursive types
  39         compat(o Type, conv bool) bool
  40         // lit returns this type's literal.  If this is a named type,
  41         // this is the unnamed underlying type.  Otherwise, this is an
  42         // identity operation.
  43         lit() Type
  44         // isBoolean returns true if this is a boolean type.
  45         isBoolean() bool
  46         // isInteger returns true if this is an integer type.
  47         isInteger() bool
  48         // isFloat returns true if this is a floating type.
  49         isFloat() bool
  50         // isIdeal returns true if this is an ideal int or float.
  51         isIdeal() bool
  52         // Zero returns a new zero value of this type.
  53         Zero() Value
  54         // String returns the string representation of this type.
  55         String() string
  56         // The position where this type was defined, if any.
  57         Pos() token.Pos
  58 }
  59
  60 type BoundedType interface {
  61         Type
  62         // minVal returns the smallest value of this type.
  63         minVal() *big.Rat
  64         // maxVal returns the largest value of this type.
  65         maxVal() *big.Rat
  66 }
  67
  68 var universePos = token.NoPos
  69
  70 /*
  71  * Type array maps.  These are used to memoize composite types.
  72  */
  73
  74 type typeArrayMapEntry struct {
  75         key  []Type
  76         v    interface{}
  77         next *typeArrayMapEntry
  78 }
  79
  80 type typeArrayMap map[uintptr]*typeArrayMapEntry
  81
  82 func hashTypeArray(key []Type) uintptr {
  83         hash := uintptr(0)
  84         for _, t := range key {
  85                 hash = hash * 33
  86                 if t == nil {
  87                         continue
  88                 }
  89                 addr := reflect.ValueOf(t).Pointer()
  90                 hash ^= addr
  91         }
  92         return hash
  93 }
  94
  95 func newTypeArrayMap() typeArrayMap { return make(map[uintptr]*typeArrayMapEntry) }
  96
  97 func (m typeArrayMap) Get(key []Type) interface{} {
  98         ent, ok := m[hashTypeArray(key)]
  99         if !ok {
 100                 return nil
 101         }
 102
 103 nextEnt:
 104         for ; ent != nil; ent = ent.next {
 105                 if len(key) != len(ent.key) {
 106                         continue
 107                 }
 108                 for i := 0; i < len(key); i++ {
 109                         if key[i] != ent.key[i] {
 110                                 continue nextEnt
 111                         }
 112                 }
 113                 // Found it
 114                 return ent.v
 115         }
 116
 117         return nil
 118 }
 119
 120 func (m typeArrayMap) Put(key []Type, v interface{}) interface{} {
 121         hash := hashTypeArray(key)
 122         ent := m[hash]
 123
 124         new := &typeArrayMapEntry{key, v, ent}
 125         m[hash] = new
 126         return v
 127 }
 128
 129 /*
 130  * Common type
 131  */
 132
 133 type commonType struct{}
 134
 135 func (commonType) isBoolean() bool { return false }
 136
 137 func (commonType) isInteger() bool { return false }
 138
 139 func (commonType) isFloat() bool { return false }
 140
 141 func (commonType) isIdeal() bool { return false }
 142
 143 func (commonType) Pos() token.Pos { return token.NoPos }
 144
 145 /*
 146  * Bool
 147  */
 148
 149 type boolType struct {
 150         commonType
 151 }
 152
 153 var BoolType = universe.DefineType("bool", universePos, &boolType{})
 154
 155 func (t *boolType) compat(o Type, conv bool) bool {
 156         _, ok := o.lit().(*boolType)
 157         return ok
 158 }
 159
 160 func (t *boolType) lit() Type { return t }
 161
 162 func (t *boolType) isBoolean() bool { return true }
 163
 164 func (boolType) String() string {
 165         // Use angle brackets as a convention for printing the
 166         // underlying, unnamed type.  This should only show up in
 167         // debug output.
 168         return "<bool>"
 169 }
 170
 171 func (t *boolType) Zero() Value {
 172         res := boolV(false)
 173         return &res
 174 }
 175
 176 /*
 177  * Uint
 178  */
 179
 180 type uintType struct {
 181         commonType
 182
 183         // 0 for architecture-dependent types
 184         Bits uint
 185         // true for uintptr, false for all others
 186         Ptr  bool
 187         name string
 188 }
 189
 190 var (
 191         Uint8Type  = universe.DefineType("uint8", universePos, &uintType{commonType{}, 8, false, "uint8"})
 192         Uint16Type = universe.DefineType("uint16", universePos, &uintType{commonType{}, 16, false, "uint16"})
 193         Uint32Type = universe.DefineType("uint32", universePos, &uintType{commonType{}, 32, false, "uint32"})
 194         Uint64Type = universe.DefineType("uint64", universePos, &uintType{commonType{}, 64, false, "uint64"})
 195
 196         UintType    = universe.DefineType("uint", universePos, &uintType{commonType{}, 0, false, "uint"})
 197         UintptrType = universe.DefineType("uintptr", universePos, &uintType{commonType{}, 0, true, "uintptr"})
 198 )
 199
 200 func (t *uintType) compat(o Type, conv bool) bool {
 201         t2, ok := o.lit().(*uintType)
 202         return ok && t == t2
 203 }
 204
 205 func (t *uintType) lit() Type { return t }
 206
 207 func (t *uintType) isInteger() bool { return true }
 208
 209 func (t *uintType) String() string { return "<" + t.name + ">" }
 210
 211 func (t *uintType) Zero() Value {
 212         switch t.Bits {
 213         case 0:
 214                 if t.Ptr {
 215                         res := uintptrV(0)
 216                         return &res
 217                 } else {
 218                         res := uintV(0)
 219                         return &res
 220                 }
 221         case 8:
 222                 res := uint8V(0)
 223                 return &res
 224         case 16:
 225                 res := uint16V(0)
 226                 return &res
 227         case 32:
 228                 res := uint32V(0)
 229                 return &res
 230         case 64:
 231                 res := uint64V(0)
 232                 return &res
 233         }
 234         panic("unexpected uint bit count")
 235 }
 236
 237 func (t *uintType) minVal() *big.Rat { return big.NewRat(0, 1) }
 238
 239 func (t *uintType) maxVal() *big.Rat {
 240         bits := t.Bits
 241         if bits == 0 {
 242                 if t.Ptr {
 243                         bits = uint(8 * unsafe.Sizeof(uintptr(0)))
 244                 } else {
 245                         bits = uint(8 * unsafe.Sizeof(uint(0)))
 246                 }
 247         }
 248         numer := big.NewInt(1)
 249         numer.Lsh(numer, bits)
 250         numer.Sub(numer, idealOne)
 251         return new(big.Rat).SetInt(numer)
 252 }
 253
 254 /*
 255  * Int
 256  */
 257
 258 type intType struct {
 259         commonType
 260
 261         // XXX(Spec) Numeric types: "There is also a set of
 262         // architecture-independent basic numeric types whose size
 263         // depends on the architecture."  Should that be
 264         // architecture-dependent?
 265
 266         // 0 for architecture-dependent types
 267         Bits uint
 268         name string
 269 }
 270
 271 var (
 272         Int8Type  = universe.DefineType("int8", universePos, &intType{commonType{}, 8, "int8"})
 273         Int16Type = universe.DefineType("int16", universePos, &intType{commonType{}, 16, "int16"})
 274         Int32Type = universe.DefineType("int32", universePos, &intType{commonType{}, 32, "int32"})
 275         Int64Type = universe.DefineType("int64", universePos, &intType{commonType{}, 64, "int64"})
 276
 277         IntType = universe.DefineType("int", universePos, &intType{commonType{}, 0, "int"})
 278 )
 279
 280 func (t *intType) compat(o Type, conv bool) bool {
 281         t2, ok := o.lit().(*intType)
 282         return ok && t == t2
 283 }
 284
 285 func (t *intType) lit() Type { return t }
 286
 287 func (t *intType) isInteger() bool { return true }
 288
 289 func (t *intType) String() string { return "<" + t.name + ">" }
 290
 291 func (t *intType) Zero() Value {
 292         switch t.Bits {
 293         case 8:
 294                 res := int8V(0)
 295                 return &res
 296         case 16:
 297                 res := int16V(0)
 298                 return &res
 299         case 32:
 300                 res := int32V(0)
 301                 return &res
 302         case 64:
 303                 res := int64V(0)
 304                 return &res
 305
 306         case 0:
 307                 res := intV(0)
 308                 return &res
 309         }
 310         panic("unexpected int bit count")
 311 }
 312
 313 func (t *intType) minVal() *big.Rat {
 314         bits := t.Bits
 315         if bits == 0 {
 316                 bits = uint(8 * unsafe.Sizeof(int(0)))
 317         }
 318         numer := big.NewInt(-1)
 319         numer.Lsh(numer, bits-1)
 320         return new(big.Rat).SetInt(numer)
 321 }
 322
 323 func (t *intType) maxVal() *big.Rat {
 324         bits := t.Bits
 325         if bits == 0 {
 326                 bits = uint(8 * unsafe.Sizeof(int(0)))
 327         }
 328         numer := big.NewInt(1)
 329         numer.Lsh(numer, bits-1)
 330         numer.Sub(numer, idealOne)
 331         return new(big.Rat).SetInt(numer)
 332 }
 333
 334 /*
 335  * Ideal int
 336  */
 337
 338 type idealIntType struct {
 339         commonType
 340 }
 341
 342 var IdealIntType Type = &idealIntType{}
 343
 344 func (t *idealIntType) compat(o Type, conv bool) bool {
 345         _, ok := o.lit().(*idealIntType)
 346         return ok
 347 }
 348
 349 func (t *idealIntType) lit() Type { return t }
 350
 351 func (t *idealIntType) isInteger() bool { return true }
 352
 353 func (t *idealIntType) isIdeal() bool { return true }
 354
 355 func (t *idealIntType) String() string { return "ideal integer" }
 356
 357 func (t *idealIntType) Zero() Value { return &idealIntV{idealZero} }
 358
 359 /*
 360  * Float
 361  */
 362
 363 type floatType struct {
 364         commonType
 365
 366         // 0 for architecture-dependent type
 367         Bits uint
 368
 369         name string
 370 }
 371
 372 var (
 373         Float32Type = universe.DefineType("float32", universePos, &floatType{commonType{}, 32, "float32"})
 374         Float64Type = universe.DefineType("float64", universePos, &floatType{commonType{}, 64, "float64"})
 375 )
 376
 377 func (t *floatType) compat(o Type, conv bool) bool {
 378         t2, ok := o.lit().(*floatType)
 379         return ok && t == t2
 380 }
 381
 382 func (t *floatType) lit() Type { return t }
 383
 384 func (t *floatType) isFloat() bool { return true }
 385
 386 func (t *floatType) String() string { return "<" + t.name + ">" }
 387
 388 func (t *floatType) Zero() Value {
 389         switch t.Bits {
 390         case 32:
 391                 res := float32V(0)
 392                 return &res
 393         case 64:
 394                 res := float64V(0)
 395                 return &res
 396         }
 397         panic("unexpected float bit count")
 398 }
 399
 400 var maxFloat32Val *big.Rat
 401 var maxFloat64Val *big.Rat
 402 var minFloat32Val *big.Rat
 403 var minFloat64Val *big.Rat
 404
 405 func (t *floatType) minVal() *big.Rat {
 406         bits := t.Bits
 407         switch bits {
 408         case 32:
 409                 return minFloat32Val
 410         case 64:
 411                 return minFloat64Val
 412         }
 413         log.Panicf("unexpected floating point bit count: %d", bits)
 414         panic("unreachable")
 415 }
 416
 417 func (t *floatType) maxVal() *big.Rat {
 418         bits := t.Bits
 419         switch bits {
 420         case 32:
 421                 return maxFloat32Val
 422         case 64:
 423                 return maxFloat64Val
 424         }
 425         log.Panicf("unexpected floating point bit count: %d", bits)
 426         panic("unreachable")
 427 }
 428
 429 /*
 430  * Ideal float
 431  */
 432
 433 type idealFloatType struct {
 434         commonType
 435 }
 436
 437 var IdealFloatType Type = &idealFloatType{}
 438
 439 func (t *idealFloatType) compat(o Type, conv bool) bool {
 440         _, ok := o.lit().(*idealFloatType)
 441         return ok
 442 }
 443
 444 func (t *idealFloatType) lit() Type { return t }
 445
 446 func (t *idealFloatType) isFloat() bool { return true }
 447
 448 func (t *idealFloatType) isIdeal() bool { return true }
 449
 450 func (t *idealFloatType) String() string { return "ideal float" }
 451
 452 func (t *idealFloatType) Zero() Value { return &idealFloatV{big.NewRat(0, 1)} }
 453
 454 /*
 455  * String
 456  */
 457
 458 type stringType struct {
 459         commonType
 460 }
 461
 462 var StringType = universe.DefineType("string", universePos, &stringType{})
 463
 464 func (t *stringType) compat(o Type, conv bool) bool {
 465         _, ok := o.lit().(*stringType)
 466         return ok
 467 }
 468
 469 func (t *stringType) lit() Type { return t }
 470
 471 func (t *stringType) String() string { return "<string>" }
 472
 473 func (t *stringType) Zero() Value {
 474         res := stringV("")
 475         return &res
 476 }
 477
 478 /*
 479  * Array
 480  */
 481
 482 type ArrayType struct {
 483         commonType
 484         Len  int64
 485         Elem Type
 486 }
 487
 488 var arrayTypes = make(map[int64]map[Type]*ArrayType)
 489
 490 // Two array types are identical if they have identical element types
 491 // and the same array length.
 492
 493 func NewArrayType(len int64, elem Type) *ArrayType {
 494         ts, ok := arrayTypes[len]
 495         if !ok {
 496                 ts = make(map[Type]*ArrayType)
 497                 arrayTypes[len] = ts
 498         }
 499         t, ok := ts[elem]
 500         if !ok {
 501                 t = &ArrayType{commonType{}, len, elem}
 502                 ts[elem] = t
 503         }
 504         return t
 505 }
 506
 507 func (t *ArrayType) compat(o Type, conv bool) bool {
 508         t2, ok := o.lit().(*ArrayType)
 509         if !ok {
 510                 return false
 511         }
 512         return t.Len == t2.Len && t.Elem.compat(t2.Elem, conv)
 513 }
 514
 515 func (t *ArrayType) lit() Type { return t }
 516
 517 func (t *ArrayType) String() string { return "[]" + t.Elem.String() }
 518
 519 func (t *ArrayType) Zero() Value {
 520         res := arrayV(make([]Value, t.Len))
 521         // TODO(austin) It's unfortunate that each element is
 522         // separately heap allocated.  We could add ZeroArray to
 523         // everything, though that doesn't help with multidimensional
 524         // arrays.  Or we could do something unsafe.  We'll have this
 525         // same problem with structs.
 526         for i := int64(0); i < t.Len; i++ {
 527                 res[i] = t.Elem.Zero()
 528         }
 529         return &res
 530 }
 531
 532 /*
 533  * Struct
 534  */
 535
 536 type StructField struct {
 537         Name      string
 538         Type      Type
 539         Anonymous bool
 540 }
 541
 542 type StructType struct {
 543         commonType
 544         Elems []StructField
 545 }
 546
 547 var structTypes = newTypeArrayMap()
 548
 549 // Two struct types are identical if they have the same sequence of
 550 // fields, and if corresponding fields have the same names and
 551 // identical types. Two anonymous fields are considered to have the
 552 // same name.
 553
 554 func NewStructType(fields []StructField) *StructType {
 555         // Start by looking up just the types
 556         fts := make([]Type, len(fields))
 557         for i, f := range fields {
 558                 fts[i] = f.Type
 559         }
 560         tMapI := structTypes.Get(fts)
 561         if tMapI == nil {
 562                 tMapI = structTypes.Put(fts, make(map[string]*StructType))
 563         }
 564         tMap := tMapI.(map[string]*StructType)
 565
 566         // Construct key for field names
 567         key := ""
 568         for _, f := range fields {
 569                 // XXX(Spec) It's not clear if struct { T } and struct
 570                 // { T T } are either identical or compatible.  The
 571                 // "Struct Types" section says that the name of that
 572                 // field is "T", which suggests that they are
 573                 // identical, but it really means that it's the name
 574                 // for the purpose of selector expressions and nothing
 575                 // else.  We decided that they should be neither
 576                 // identical or compatible.
 577                 if f.Anonymous {
 578                         key += "!"
 579                 }
 580                 key += f.Name + " "
 581         }
 582
 583         // XXX(Spec) Do the tags also have to be identical for the
 584         // types to be identical?  I certainly hope so, because
 585         // otherwise, this is the only case where two distinct type
 586         // objects can represent identical types.
 587
 588         t, ok := tMap[key]
 589         if !ok {
 590                 // Create new struct type
 591                 t = &StructType{commonType{}, fields}
 592                 tMap[key] = t
 593         }
 594         return t
 595 }
 596
 597 func (t *StructType) compat(o Type, conv bool) bool {
 598         t2, ok := o.lit().(*StructType)
 599         if !ok {
 600                 return false
 601         }
 602         if len(t.Elems) != len(t2.Elems) {
 603                 return false
 604         }
 605         for i, e := range t.Elems {
 606                 e2 := t2.Elems[i]
 607                 // XXX(Spec) An anonymous and a non-anonymous field
 608                 // are neither identical nor compatible.
 609                 if e.Anonymous != e2.Anonymous ||
 610                         (!e.Anonymous && e.Name != e2.Name) ||
 611                         !e.Type.compat(e2.Type, conv) {
 612                         return false
 613                 }
 614         }
 615         return true
 616 }
 617
 618 func (t *StructType) lit() Type { return t }
 619
 620 func (t *StructType) String() string {
 621         s := "struct {"
 622         for i, f := range t.Elems {
 623                 if i > 0 {
 624                         s += "; "
 625                 }
 626                 if !f.Anonymous {
 627                         s += f.Name + " "
 628                 }
 629                 s += f.Type.String()
 630         }
 631         return s + "}"
 632 }
 633
 634 func (t *StructType) Zero() Value {
 635         res := structV(make([]Value, len(t.Elems)))
 636         for i, f := range t.Elems {
 637                 res[i] = f.Type.Zero()
 638         }
 639         return &res
 640 }
 641
 642 /*
 643  * Pointer
 644  */
 645
 646 type PtrType struct {
 647         commonType
 648         Elem Type
 649 }
 650
 651 var ptrTypes = make(map[Type]*PtrType)
 652
 653 // Two pointer types are identical if they have identical base types.
 654
 655 func NewPtrType(elem Type) *PtrType {
 656         t, ok := ptrTypes[elem]
 657         if !ok {
 658                 t = &PtrType{commonType{}, elem}
 659                 ptrTypes[elem] = t
 660         }
 661         return t
 662 }
 663
 664 func (t *PtrType) compat(o Type, conv bool) bool {
 665         t2, ok := o.lit().(*PtrType)
 666         if !ok {
 667                 return false
 668         }
 669         return t.Elem.compat(t2.Elem, conv)
 670 }
 671
 672 func (t *PtrType) lit() Type { return t }
 673
 674 func (t *PtrType) String() string { return "*" + t.Elem.String() }
 675
 676 func (t *PtrType) Zero() Value { return &ptrV{nil} }
 677
 678 /*
 679  * Function
 680  */
 681
 682 type FuncType struct {
 683         commonType
 684         // TODO(austin) Separate receiver Type for methods?
 685         In       []Type
 686         Variadic bool
 687         Out      []Type
 688         builtin  string
 689 }
 690
 691 var funcTypes = newTypeArrayMap()
 692 var variadicFuncTypes = newTypeArrayMap()
 693
 694 // Create singleton function types for magic built-in functions
 695 var (
 696         capType     = &FuncType{builtin: "cap"}
 697         closeType   = &FuncType{builtin: "close"}
 698         closedType  = &FuncType{builtin: "closed"}
 699         lenType     = &FuncType{builtin: "len"}
 700         makeType    = &FuncType{builtin: "make"}
 701         newType     = &FuncType{builtin: "new"}
 702         panicType   = &FuncType{builtin: "panic"}
 703         printType   = &FuncType{builtin: "print"}
 704         printlnType = &FuncType{builtin: "println"}
 705         copyType    = &FuncType{builtin: "copy"}
 706 )
 707
 708 // Two function types are identical if they have the same number of
 709 // parameters and result values and if corresponding parameter and
 710 // result types are identical. All "..." parameters have identical
 711 // type. Parameter and result names are not required to match.
 712
 713 func NewFuncType(in []Type, variadic bool, out []Type) *FuncType {
 714         inMap := funcTypes
 715         if variadic {
 716                 inMap = variadicFuncTypes
 717         }
 718
 719         outMapI := inMap.Get(in)
 720         if outMapI == nil {
 721                 outMapI = inMap.Put(in, newTypeArrayMap())
 722         }
 723         outMap := outMapI.(typeArrayMap)
 724
 725         tI := outMap.Get(out)
 726         if tI != nil {
 727                 return tI.(*FuncType)
 728         }
 729
 730         t := &FuncType{commonType{}, in, variadic, out, ""}
 731         outMap.Put(out, t)
 732         return t
 733 }
 734
 735 func (t *FuncType) compat(o Type, conv bool) bool {
 736         t2, ok := o.lit().(*FuncType)
 737         if !ok {
 738                 return false
 739         }
 740         if len(t.In) != len(t2.In) || t.Variadic != t2.Variadic || len(t.Out) != len(t2.Out) {
 741                 return false
 742         }
 743         for i := range t.In {
 744                 if !t.In[i].compat(t2.In[i], conv) {
 745                         return false
 746                 }
 747         }
 748         for i := range t.Out {
 749                 if !t.Out[i].compat(t2.Out[i], conv) {
 750                         return false
 751                 }
 752         }
 753         return true
 754 }
 755
 756 func (t *FuncType) lit() Type { return t }
 757
 758 func typeListString(ts []Type, ns []*ast.Ident) string {
 759         s := ""
 760         for i, t := range ts {
 761                 if i > 0 {
 762                         s += ", "
 763                 }
 764                 if ns != nil && ns[i] != nil {
 765                         s += ns[i].Name + " "
 766                 }
 767                 if t == nil {
 768                         // Some places use nil types to represent errors
 769                         s += "<none>"
 770                 } else {
 771                         s += t.String()
 772                 }
 773         }
 774         return s
 775 }
 776
 777 func (t *FuncType) String() string {
 778         if t.builtin != "" {
 779                 return "built-in function " + t.builtin
 780         }
 781         args := typeListString(t.In, nil)
 782         if t.Variadic {
 783                 if len(args) > 0 {
 784                         args += ", "
 785                 }
 786                 args += "..."
 787         }
 788         s := "func(" + args + ")"
 789         if len(t.Out) > 0 {
 790                 s += " (" + typeListString(t.Out, nil) + ")"
 791         }
 792         return s
 793 }
 794
 795 func (t *FuncType) Zero() Value { return &funcV{nil} }
 796
 797 type FuncDecl struct {
 798         Type *FuncType
 799         Name *ast.Ident // nil for function literals
 800         // InNames will be one longer than Type.In if this function is
 801         // variadic.
 802         InNames  []*ast.Ident
 803         OutNames []*ast.Ident
 804 }
 805
 806 func (t *FuncDecl) String() string {
 807         s := "func"
 808         if t.Name != nil {
 809                 s += " " + t.Name.Name
 810         }
 811         s += funcTypeString(t.Type, t.InNames, t.OutNames)
 812         return s
 813 }
 814
 815 func funcTypeString(ft *FuncType, ins []*ast.Ident, outs []*ast.Ident) string {
 816         s := "("
 817         s += typeListString(ft.In, ins)
 818         if ft.Variadic {
 819                 if len(ft.In) > 0 {
 820                         s += ", "
 821                 }
 822                 s += "..."
 823         }
 824         s += ")"
 825         if len(ft.Out) > 0 {
 826                 s += " (" + typeListString(ft.Out, outs) + ")"
 827         }
 828         return s
 829 }
 830
 831 /*
 832  * Interface
 833  */
 834
 835 // TODO(austin) Interface values, types, and type compilation are
 836 // implemented, but none of the type checking or semantics of
 837 // interfaces are.
 838
 839 type InterfaceType struct {
 840         commonType
 841         // TODO(austin) This should be a map from names to
 842         // *FuncType's.  We only need the sorted list for generating
 843         // the type map key.  It's detrimental for everything else.
 844         methods []IMethod
 845 }
 846
 847 type IMethod struct {
 848         Name string
 849         Type *FuncType
 850 }
 851
 852 var interfaceTypes = newTypeArrayMap()
 853
 854 func NewInterfaceType(methods []IMethod, embeds []*InterfaceType) *InterfaceType {
 855         // Count methods of embedded interfaces
 856         nMethods := len(methods)
 857         for _, e := range embeds {
 858                 nMethods += len(e.methods)
 859         }
 860
 861         // Combine methods
 862         allMethods := make([]IMethod, nMethods)
 863         copy(allMethods, methods)
 864         n := len(methods)
 865         for _, e := range embeds {
 866                 for _, m := range e.methods {
 867                         allMethods[n] = m
 868                         n++
 869                 }
 870         }
 871
 872         // Sort methods
 873         sort.Sort(iMethodSorter(allMethods))
 874
 875         mts := make([]Type, len(allMethods))
 876         for i, m := range methods {
 877                 mts[i] = m.Type
 878         }
 879         tMapI := interfaceTypes.Get(mts)
 880         if tMapI == nil {
 881                 tMapI = interfaceTypes.Put(mts, make(map[string]*InterfaceType))
 882         }
 883         tMap := tMapI.(map[string]*InterfaceType)
 884
 885         key := ""
 886         for _, m := range allMethods {
 887                 key += m.Name + " "
 888         }
 889
 890         t, ok := tMap[key]
 891         if !ok {
 892                 t = &InterfaceType{commonType{}, allMethods}
 893                 tMap[key] = t
 894         }
 895         return t
 896 }
 897
 898 type iMethodSorter []IMethod
 899
 900 func (s iMethodSorter) Less(a, b int) bool { return s[a].Name < s[b].Name }
 901
 902 func (s iMethodSorter) Swap(a, b int) { s[a], s[b] = s[b], s[a] }
 903
 904 func (s iMethodSorter) Len() int { return len(s) }
 905
 906 func (t *InterfaceType) compat(o Type, conv bool) bool {
 907         t2, ok := o.lit().(*InterfaceType)
 908         if !ok {
 909                 return false
 910         }
 911         if len(t.methods) != len(t2.methods) {
 912                 return false
 913         }
 914         for i, e := range t.methods {
 915                 e2 := t2.methods[i]
 916                 if e.Name != e2.Name || !e.Type.compat(e2.Type, conv) {
 917                         return false
 918                 }
 919         }
 920         return true
 921 }
 922
 923 func (t *InterfaceType) lit() Type { return t }
 924
 925 func (t *InterfaceType) String() string {
 926         // TODO(austin) Instead of showing embedded interfaces, this
 927         // shows their methods.
 928         s := "interface {"
 929         for i, m := range t.methods {
 930                 if i > 0 {
 931                         s += "; "
 932                 }
 933                 s += m.Name + funcTypeString(m.Type, nil, nil)
 934         }
 935         return s + "}"
 936 }
 937
 938 // implementedBy tests if o implements t, returning nil, true if it does.
 939 // Otherwise, it returns a method of t that o is missing and false.
 940 func (t *InterfaceType) implementedBy(o Type) (*IMethod, bool) {
 941         if len(t.methods) == 0 {
 942                 return nil, true
 943         }
 944
 945         // The methods of a named interface types are those of the
 946         // underlying type.
 947         if it, ok := o.lit().(*InterfaceType); ok {
 948                 o = it
 949         }
 950
 951         // XXX(Spec) Interface types: "A type implements any interface
 952         // comprising any subset of its methods" It's unclear if
 953         // methods must have identical or compatible types.  6g
 954         // requires identical types.
 955
 956         switch o := o.(type) {
 957         case *NamedType:
 958                 for _, tm := range t.methods {
 959                         sm, ok := o.methods[tm.Name]
 960                         if !ok || sm.decl.Type != tm.Type {
 961                                 return &tm, false
 962                         }
 963                 }
 964                 return nil, true
 965
 966         case *InterfaceType:
 967                 var ti, oi int
 968                 for ti < len(t.methods) && oi < len(o.methods) {
 969                         tm, om := &t.methods[ti], &o.methods[oi]
 970                         switch {
 971                         case tm.Name == om.Name:
 972                                 if tm.Type != om.Type {
 973                                         return tm, false
 974                                 }
 975                                 ti++
 976                                 oi++
 977                         case tm.Name > om.Name:
 978                                 oi++
 979                         default:
 980                                 return tm, false
 981                         }
 982                 }
 983                 if ti < len(t.methods) {
 984                         return &t.methods[ti], false
 985                 }
 986                 return nil, true
 987         }
 988
 989         return &t.methods[0], false
 990 }
 991
 992 func (t *InterfaceType) Zero() Value { return &interfaceV{} }
 993
 994 /*
 995  * Slice
 996  */
 997
 998 type SliceType struct {
 999         commonType
1000         Elem Type
1001 }
1002
1003 var sliceTypes = make(map[Type]*SliceType)
1004
1005 // Two slice types are identical if they have identical element types.
1006
1007 func NewSliceType(elem Type) *SliceType {
1008         t, ok := sliceTypes[elem]
1009         if !ok {
1010                 t = &SliceType{commonType{}, elem}
1011                 sliceTypes[elem] = t
1012         }
1013         return t
1014 }
1015
1016 func (t *SliceType) compat(o Type, conv bool) bool {
1017         t2, ok := o.lit().(*SliceType)
1018         if !ok {
1019                 return false
1020         }
1021         return t.Elem.compat(t2.Elem, conv)
1022 }
1023
1024 func (t *SliceType) lit() Type { return t }
1025
1026 func (t *SliceType) String() string { return "[]" + t.Elem.String() }
1027
1028 func (t *SliceType) Zero() Value {
1029         // The value of an uninitialized slice is nil. The length and
1030         // capacity of a nil slice are 0.
1031         return &sliceV{Slice{nil, 0, 0}}
1032 }
1033
1034 /*
1035  * Map type
1036  */
1037
1038 type MapType struct {
1039         commonType
1040         Key  Type
1041         Elem Type
1042 }
1043
1044 var mapTypes = make(map[Type]map[Type]*MapType)
1045
1046 func NewMapType(key Type, elem Type) *MapType {
1047         ts, ok := mapTypes[key]
1048         if !ok {
1049                 ts = make(map[Type]*MapType)
1050                 mapTypes[key] = ts
1051         }
1052         t, ok := ts[elem]
1053         if !ok {
1054                 t = &MapType{commonType{}, key, elem}
1055                 ts[elem] = t
1056         }
1057         return t
1058 }
1059
1060 func (t *MapType) compat(o Type, conv bool) bool {
1061         t2, ok := o.lit().(*MapType)
1062         if !ok {
1063                 return false
1064         }
1065         return t.Elem.compat(t2.Elem, conv) && t.Key.compat(t2.Key, conv)
1066 }
1067
1068 func (t *MapType) lit() Type { return t }
1069
1070 func (t *MapType) String() string { return "map[" + t.Key.String() + "] " + t.Elem.String() }
1071
1072 func (t *MapType) Zero() Value {
1073         // The value of an uninitialized map is nil.
1074         return &mapV{nil}
1075 }
1076
1077 /*
1078 type ChanType struct {
1079         // TODO(austin)
1080 }
1081 */
1082
1083 /*
1084  * Named types
1085  */
1086
1087 type Method struct {
1088         decl *FuncDecl
1089         fn   Func
1090 }
1091
1092 type NamedType struct {
1093         NamePos token.Pos
1094         Name    string
1095         // Underlying type.  If incomplete is true, this will be nil.
1096         // If incomplete is false and this is still nil, then this is
1097         // a placeholder type representing an error.
1098         Def Type
1099         // True while this type is being defined.
1100         incomplete bool
1101         methods    map[string]Method
1102 }
1103
1104 // TODO(austin) This is temporarily needed by the debugger's remote
1105 // type parser.  This should only be possible with block.DefineType.
1106 func NewNamedType(name string) *NamedType {
1107         return &NamedType{token.NoPos, name, nil, true, make(map[string]Method)}
1108 }
1109
1110 func (t *NamedType) Pos() token.Pos {
1111         return t.NamePos
1112 }
1113
1114 func (t *NamedType) Complete(def Type) {
1115         if !t.incomplete {
1116                 log.Panicf("cannot complete already completed NamedType %+v", *t)
1117         }
1118         // We strip the name from def because multiple levels of
1119         // naming are useless.
1120         if ndef, ok := def.(*NamedType); ok {
1121                 def = ndef.Def
1122         }
1123         t.Def = def
1124         t.incomplete = false
1125 }
1126
1127 func (t *NamedType) compat(o Type, conv bool) bool {
1128         t2, ok := o.(*NamedType)
1129         if ok {
1130                 if conv {
1131                         // Two named types are conversion compatible
1132                         // if their literals are conversion
1133                         // compatible.
1134                         return t.Def.compat(t2.Def, conv)
1135                 } else {
1136                         // Two named types are compatible if their
1137                         // type names originate in the same type
1138                         // declaration.
1139                         return t == t2
1140                 }
1141         }
1142         // A named and an unnamed type are compatible if the
1143         // respective type literals are compatible.
1144         return o.compat(t.Def, conv)
1145 }
1146
1147 func (t *NamedType) lit() Type { return t.Def.lit() }
1148
1149 func (t *NamedType) isBoolean() bool { return t.Def.isBoolean() }
1150
1151 func (t *NamedType) isInteger() bool { return t.Def.isInteger() }
1152
1153 func (t *NamedType) isFloat() bool { return t.Def.isFloat() }
1154
1155 func (t *NamedType) isIdeal() bool { return false }
1156
1157 func (t *NamedType) String() string { return t.Name }
1158
1159 func (t *NamedType) Zero() Value { return t.Def.Zero() }
1160
1161 /*
1162  * Multi-valued type
1163  */
1164
1165 // MultiType is a special type used for multi-valued expressions, akin
1166 // to a tuple type.  It's not generally accessible within the
1167 // language.
1168 type MultiType struct {
1169         commonType
1170         Elems []Type
1171 }
1172
1173 var multiTypes = newTypeArrayMap()
1174
1175 func NewMultiType(elems []Type) *MultiType {
1176         if t := multiTypes.Get(elems); t != nil {
1177                 return t.(*MultiType)
1178         }
1179
1180         t := &MultiType{commonType{}, elems}
1181         multiTypes.Put(elems, t)
1182         return t
1183 }
1184
1185 func (t *MultiType) compat(o Type, conv bool) bool {
1186         t2, ok := o.lit().(*MultiType)
1187         if !ok {
1188                 return false
1189         }
1190         if len(t.Elems) != len(t2.Elems) {
1191                 return false
1192         }
1193         for i := range t.Elems {
1194                 if !t.Elems[i].compat(t2.Elems[i], conv) {
1195                         return false
1196                 }
1197         }
1198         return true
1199 }
1200
1201 var EmptyType Type = NewMultiType([]Type{})
1202
1203 func (t *MultiType) lit() Type { return t }
1204
1205 func (t *MultiType) String() string {
1206         if len(t.Elems) == 0 {
1207                 return "<none>"
1208         }
1209         return typeListString(t.Elems, nil)
1210 }
1211
1212 func (t *MultiType) Zero() Value {
1213         res := make([]Value, len(t.Elems))
1214         for i, t := range t.Elems {
1215                 res[i] = t.Zero()
1216         }
1217         return multiV(res)
1218 }
1219
1220 /*
1221  * Initialize the universe
1222  */
1223
1224 func init() {
1225         numer := big.NewInt(0xffffff)
1226         numer.Lsh(numer, 127-23)
1227         maxFloat32Val = new(big.Rat).SetInt(numer)
1228         numer.SetInt64(0x1fffffffffffff)
1229         numer.Lsh(numer, 1023-52)
1230         maxFloat64Val = new(big.Rat).SetInt(numer)
1231         minFloat32Val = new(big.Rat).Neg(maxFloat32Val)
1232         minFloat64Val = new(big.Rat).Neg(maxFloat64Val)
1233
1234         // To avoid portability issues all numeric types are distinct
1235         // except byte, which is an alias for uint8.
1236
1237         // Make byte an alias for the named type uint8.  Type aliases
1238         // are otherwise impossible in Go, so just hack it here.
1239         universe.defs["byte"] = universe.defs["uint8"]
1240
1241         // Built-in functions
1242         universe.DefineConst("cap", universePos, capType, nil)
1243         universe.DefineConst("close", universePos, closeType, nil)
1244         universe.DefineConst("closed", universePos, closedType, nil)
1245         universe.DefineConst("copy", universePos, copyType, nil)
1246         universe.DefineConst("len", universePos, lenType, nil)
1247         universe.DefineConst("make", universePos, makeType, nil)
1248         universe.DefineConst("new", universePos, newType, nil)
1249         universe.DefineConst("panic", universePos, panicType, nil)
1250         universe.DefineConst("print", universePos, printType, nil)
1251         universe.DefineConst("println", universePos, printlnType, nil)
1252 }