libgo/go/exp/types/types.go

   1 // Copyright 2011 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 types declares the types used to represent Go types
   6 // (UNDER CONSTRUCTION). ANY AND ALL PARTS MAY CHANGE.
   7 //
   8 package types
   9
  10 import (
  11         "go/ast"
  12         "sort"
  13 )
  14
  15 // All types implement the Type interface.
  16 type Type interface {
  17         isType()
  18 }
  19
  20 // All concrete types embed ImplementsType which
  21 // ensures that all types implement the Type interface.
  22 type ImplementsType struct{}
  23
  24 func (t *ImplementsType) isType() {}
  25
  26 // A Bad type is a non-nil placeholder type when we don't know a type.
  27 type Bad struct {
  28         ImplementsType
  29         Msg string // for better error reporting/debugging
  30 }
  31
  32 // A Basic represents a (unnamed) basic type.
  33 type Basic struct {
  34         ImplementsType
  35         // TODO(gri) need a field specifying the exact basic type
  36 }
  37
  38 // An Array represents an array type [Len]Elt.
  39 type Array struct {
  40         ImplementsType
  41         Len uint64
  42         Elt Type
  43 }
  44
  45 // A Slice represents a slice type []Elt.
  46 type Slice struct {
  47         ImplementsType
  48         Elt Type
  49 }
  50
  51 // A Struct represents a struct type struct{...}.
  52 // Anonymous fields are represented by objects with empty names.
  53 type Struct struct {
  54         ImplementsType
  55         Fields ObjList  // struct fields; or nil
  56         Tags   []string // corresponding tags; or nil
  57         // TODO(gri) This type needs some rethinking:
  58         // - at the moment anonymous fields are marked with "" object names,
  59         //   and their names have to be reconstructed
  60         // - there is no scope for fast lookup (but the parser creates one)
  61 }
  62
  63 // A Pointer represents a pointer type *Base.
  64 type Pointer struct {
  65         ImplementsType
  66         Base Type
  67 }
  68
  69 // A Func represents a function type func(...) (...).
  70 // Unnamed parameters are represented by objects with empty names.
  71 type Func struct {
  72         ImplementsType
  73         Recv       *ast.Object // nil if not a method
  74         Params     ObjList     // (incoming) parameters from left to right; or nil
  75         Results    ObjList     // (outgoing) results from left to right; or nil
  76         IsVariadic bool        // true if the last parameter's type is of the form ...T
  77 }
  78
  79 // An Interface represents an interface type interface{...}.
  80 type Interface struct {
  81         ImplementsType
  82         Methods ObjList // interface methods sorted by name; or nil
  83 }
  84
  85 // A Map represents a map type map[Key]Elt.
  86 type Map struct {
  87         ImplementsType
  88         Key, Elt Type
  89 }
  90
  91 // A Chan represents a channel type chan Elt, <-chan Elt, or chan<-Elt.
  92 type Chan struct {
  93         ImplementsType
  94         Dir ast.ChanDir
  95         Elt Type
  96 }
  97
  98 // A Name represents a named type as declared in a type declaration.
  99 type Name struct {
 100         ImplementsType
 101         Underlying Type        // nil if not fully declared
 102         Obj        *ast.Object // corresponding declared object
 103         // TODO(gri) need to remember fields and methods.
 104 }
 105
 106 // If typ is a pointer type, Deref returns the pointer's base type;
 107 // otherwise it returns typ.
 108 func Deref(typ Type) Type {
 109         if typ, ok := typ.(*Pointer); ok {
 110                 return typ.Base
 111         }
 112         return typ
 113 }
 114
 115 // Underlying returns the underlying type of a type.
 116 func Underlying(typ Type) Type {
 117         if typ, ok := typ.(*Name); ok {
 118                 utyp := typ.Underlying
 119                 if _, ok := utyp.(*Basic); !ok {
 120                         return utyp
 121                 }
 122                 // the underlying type of a type name referring
 123                 // to an (untyped) basic type is the basic type
 124                 // name
 125         }
 126         return typ
 127 }
 128
 129 // An ObjList represents an ordered (in some fashion) list of objects.
 130 type ObjList []*ast.Object
 131
 132 // ObjList implements sort.Interface.
 133 func (list ObjList) Len() int           { return len(list) }
 134 func (list ObjList) Less(i, j int) bool { return list[i].Name < list[j].Name }
 135 func (list ObjList) Swap(i, j int)      { list[i], list[j] = list[j], list[i] }
 136
 137 // Sort sorts an object list by object name.
 138 func (list ObjList) Sort() { sort.Sort(list) }
 139
 140 // identicalTypes returns true if both lists a and b have the
 141 // same length and corresponding objects have identical types.
 142 func identicalTypes(a, b ObjList) bool {
 143         if len(a) == len(b) {
 144                 for i, x := range a {
 145                         y := b[i]
 146                         if !Identical(x.Type.(Type), y.Type.(Type)) {
 147                                 return false
 148                         }
 149                 }
 150                 return true
 151         }
 152         return false
 153 }
 154
 155 // Identical returns true if two types are identical.
 156 func Identical(x, y Type) bool {
 157         if x == y {
 158                 return true
 159         }
 160
 161         switch x := x.(type) {
 162         case *Bad:
 163                 // A Bad type is always identical to any other type
 164                 // (to avoid spurious follow-up errors).
 165                 return true
 166
 167         case *Basic:
 168                 if y, ok := y.(*Basic); ok {
 169                         panic("unimplemented")
 170                         _ = y
 171                 }
 172
 173         case *Array:
 174                 // Two array types are identical if they have identical element types
 175                 // and the same array length.
 176                 if y, ok := y.(*Array); ok {
 177                         return x.Len == y.Len && Identical(x.Elt, y.Elt)
 178                 }
 179
 180         case *Slice:
 181                 // Two slice types are identical if they have identical element types.
 182                 if y, ok := y.(*Slice); ok {
 183                         return Identical(x.Elt, y.Elt)
 184                 }
 185
 186         case *Struct:
 187                 // Two struct types are identical if they have the same sequence of fields,
 188                 // and if corresponding fields have the same names, and identical types,
 189                 // and identical tags. Two anonymous fields are considered to have the same
 190                 // name. Lower-case field names from different packages are always different.
 191                 if y, ok := y.(*Struct); ok {
 192                         // TODO(gri) handle structs from different packages
 193                         if identicalTypes(x.Fields, y.Fields) {
 194                                 for i, f := range x.Fields {
 195                                         g := y.Fields[i]
 196                                         if f.Name != g.Name || x.Tags[i] != y.Tags[i] {
 197                                                 return false
 198                                         }
 199                                 }
 200                                 return true
 201                         }
 202                 }
 203
 204         case *Pointer:
 205                 // Two pointer types are identical if they have identical base types.
 206                 if y, ok := y.(*Pointer); ok {
 207                         return Identical(x.Base, y.Base)
 208                 }
 209
 210         case *Func:
 211                 // Two function types are identical if they have the same number of parameters
 212                 // and result values, corresponding parameter and result types are identical,
 213                 // and either both functions are variadic or neither is. Parameter and result
 214                 // names are not required to match.
 215                 if y, ok := y.(*Func); ok {
 216                         return identicalTypes(x.Params, y.Params) &&
 217                                 identicalTypes(x.Results, y.Results) &&
 218                                 x.IsVariadic == y.IsVariadic
 219                 }
 220
 221         case *Interface:
 222                 // Two interface types are identical if they have the same set of methods with
 223                 // the same names and identical function types. Lower-case method names from
 224                 // different packages are always different. The order of the methods is irrelevant.
 225                 if y, ok := y.(*Interface); ok {
 226                         return identicalTypes(x.Methods, y.Methods) // methods are sorted
 227                 }
 228
 229         case *Map:
 230                 // Two map types are identical if they have identical key and value types.
 231                 if y, ok := y.(*Map); ok {
 232                         return Identical(x.Key, y.Key) && Identical(x.Elt, y.Elt)
 233                 }
 234
 235         case *Chan:
 236                 // Two channel types are identical if they have identical value types
 237                 // and the same direction.
 238                 if y, ok := y.(*Chan); ok {
 239                         return x.Dir == y.Dir && Identical(x.Elt, y.Elt)
 240                 }
 241
 242         case *Name:
 243                 // Two named types are identical if their type names originate
 244                 // in the same type declaration.
 245                 if y, ok := y.(*Name); ok {
 246                         return x.Obj == y.Obj ||
 247                                 // permit bad objects to be equal to avoid
 248                                 // follow up errors
 249                                 x.Obj != nil && x.Obj.Kind == ast.Bad ||
 250                                 y.Obj != nil && y.Obj.Kind == ast.Bad
 251                 }
 252         }
 253
 254         return false
 255 }