libgo/go/go/types/predicates.go

   1 // Copyright 2012 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 // This file implements commonly used type predicates.
   6
   7 package types
   8
   9 import "sort"
  10
  11 func isNamed(typ Type) bool {
  12         if _, ok := typ.(*Basic); ok {
  13                 return ok
  14         }
  15         _, ok := typ.(*Named)
  16         return ok
  17 }
  18
  19 func isBoolean(typ Type) bool {
  20         t, ok := typ.Underlying().(*Basic)
  21         return ok && t.info&IsBoolean != 0
  22 }
  23
  24 func isInteger(typ Type) bool {
  25         t, ok := typ.Underlying().(*Basic)
  26         return ok && t.info&IsInteger != 0
  27 }
  28
  29 func isUnsigned(typ Type) bool {
  30         t, ok := typ.Underlying().(*Basic)
  31         return ok && t.info&IsUnsigned != 0
  32 }
  33
  34 func isFloat(typ Type) bool {
  35         t, ok := typ.Underlying().(*Basic)
  36         return ok && t.info&IsFloat != 0
  37 }
  38
  39 func isComplex(typ Type) bool {
  40         t, ok := typ.Underlying().(*Basic)
  41         return ok && t.info&IsComplex != 0
  42 }
  43
  44 func isNumeric(typ Type) bool {
  45         t, ok := typ.Underlying().(*Basic)
  46         return ok && t.info&IsNumeric != 0
  47 }
  48
  49 func isString(typ Type) bool {
  50         t, ok := typ.Underlying().(*Basic)
  51         return ok && t.info&IsString != 0
  52 }
  53
  54 func isTyped(typ Type) bool {
  55         t, ok := typ.Underlying().(*Basic)
  56         return !ok || t.info&IsUntyped == 0
  57 }
  58
  59 func isUntyped(typ Type) bool {
  60         t, ok := typ.Underlying().(*Basic)
  61         return ok && t.info&IsUntyped != 0
  62 }
  63
  64 func isOrdered(typ Type) bool {
  65         t, ok := typ.Underlying().(*Basic)
  66         return ok && t.info&IsOrdered != 0
  67 }
  68
  69 func isConstType(typ Type) bool {
  70         t, ok := typ.Underlying().(*Basic)
  71         return ok && t.info&IsConstType != 0
  72 }
  73
  74 // IsInterface reports whether typ is an interface type.
  75 func IsInterface(typ Type) bool {
  76         _, ok := typ.Underlying().(*Interface)
  77         return ok
  78 }
  79
  80 // Comparable reports whether values of type T are comparable.
  81 func Comparable(T Type) bool {
  82         switch t := T.Underlying().(type) {
  83         case *Basic:
  84                 // assume invalid types to be comparable
  85                 // to avoid follow-up errors
  86                 return t.kind != UntypedNil
  87         case *Pointer, *Interface, *Chan:
  88                 return true
  89         case *Struct:
  90                 for _, f := range t.fields {
  91                         if !Comparable(f.typ) {
  92                                 return false
  93                         }
  94                 }
  95                 return true
  96         case *Array:
  97                 return Comparable(t.elem)
  98         }
  99         return false
 100 }
 101
 102 // hasNil reports whether a type includes the nil value.
 103 func hasNil(typ Type) bool {
 104         switch t := typ.Underlying().(type) {
 105         case *Basic:
 106                 return t.kind == UnsafePointer
 107         case *Slice, *Pointer, *Signature, *Interface, *Map, *Chan:
 108                 return true
 109         }
 110         return false
 111 }
 112
 113 // Identical reports whether x and y are identical.
 114 func Identical(x, y Type) bool {
 115         return identical(x, y, true, nil)
 116 }
 117
 118 // IdenticalIgnoreTags reports whether x and y are identical if tags are ignored.
 119 func IdenticalIgnoreTags(x, y Type) bool {
 120         return identical(x, y, false, nil)
 121 }
 122
 123 // An ifacePair is a node in a stack of interface type pairs compared for identity.
 124 type ifacePair struct {
 125         x, y *Interface
 126         prev *ifacePair
 127 }
 128
 129 func (p *ifacePair) identical(q *ifacePair) bool {
 130         return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x
 131 }
 132
 133 func identical(x, y Type, cmpTags bool, p *ifacePair) bool {
 134         if x == y {
 135                 return true
 136         }
 137
 138         switch x := x.(type) {
 139         case *Basic:
 140                 // Basic types are singletons except for the rune and byte
 141                 // aliases, thus we cannot solely rely on the x == y check
 142                 // above. See also comment in TypeName.IsAlias.
 143                 if y, ok := y.(*Basic); ok {
 144                         return x.kind == y.kind
 145                 }
 146
 147         case *Array:
 148                 // Two array types are identical if they have identical element types
 149                 // and the same array length.
 150                 if y, ok := y.(*Array); ok {
 151                         return x.len == y.len && identical(x.elem, y.elem, cmpTags, p)
 152                 }
 153
 154         case *Slice:
 155                 // Two slice types are identical if they have identical element types.
 156                 if y, ok := y.(*Slice); ok {
 157                         return identical(x.elem, y.elem, cmpTags, p)
 158                 }
 159
 160         case *Struct:
 161                 // Two struct types are identical if they have the same sequence of fields,
 162                 // and if corresponding fields have the same names, and identical types,
 163                 // and identical tags. Two anonymous fields are considered to have the same
 164                 // name. Lower-case field names from different packages are always different.
 165                 if y, ok := y.(*Struct); ok {
 166                         if x.NumFields() == y.NumFields() {
 167                                 for i, f := range x.fields {
 168                                         g := y.fields[i]
 169                                         if f.anonymous != g.anonymous ||
 170                                                 cmpTags && x.Tag(i) != y.Tag(i) ||
 171                                                 !f.sameId(g.pkg, g.name) ||
 172                                                 !identical(f.typ, g.typ, cmpTags, p) {
 173                                                 return false
 174                                         }
 175                                 }
 176                                 return true
 177                         }
 178                 }
 179
 180         case *Pointer:
 181                 // Two pointer types are identical if they have identical base types.
 182                 if y, ok := y.(*Pointer); ok {
 183                         return identical(x.base, y.base, cmpTags, p)
 184                 }
 185
 186         case *Tuple:
 187                 // Two tuples types are identical if they have the same number of elements
 188                 // and corresponding elements have identical types.
 189                 if y, ok := y.(*Tuple); ok {
 190                         if x.Len() == y.Len() {
 191                                 if x != nil {
 192                                         for i, v := range x.vars {
 193                                                 w := y.vars[i]
 194                                                 if !identical(v.typ, w.typ, cmpTags, p) {
 195                                                         return false
 196                                                 }
 197                                         }
 198                                 }
 199                                 return true
 200                         }
 201                 }
 202
 203         case *Signature:
 204                 // Two function types are identical if they have the same number of parameters
 205                 // and result values, corresponding parameter and result types are identical,
 206                 // and either both functions are variadic or neither is. Parameter and result
 207                 // names are not required to match.
 208                 if y, ok := y.(*Signature); ok {
 209                         return x.variadic == y.variadic &&
 210                                 identical(x.params, y.params, cmpTags, p) &&
 211                                 identical(x.results, y.results, cmpTags, p)
 212                 }
 213
 214         case *Interface:
 215                 // Two interface types are identical if they have the same set of methods with
 216                 // the same names and identical function types. Lower-case method names from
 217                 // different packages are always different. The order of the methods is irrelevant.
 218                 if y, ok := y.(*Interface); ok {
 219                         a := x.allMethods
 220                         b := y.allMethods
 221                         if len(a) == len(b) {
 222                                 // Interface types are the only types where cycles can occur
 223                                 // that are not "terminated" via named types; and such cycles
 224                                 // can only be created via method parameter types that are
 225                                 // anonymous interfaces (directly or indirectly) embedding
 226                                 // the current interface. Example:
 227                                 //
 228                                 //    type T interface {
 229                                 //        m() interface{T}
 230                                 //    }
 231                                 //
 232                                 // If two such (differently named) interfaces are compared,
 233                                 // endless recursion occurs if the cycle is not detected.
 234                                 //
 235                                 // If x and y were compared before, they must be equal
 236                                 // (if they were not, the recursion would have stopped);
 237                                 // search the ifacePair stack for the same pair.
 238                                 //
 239                                 // This is a quadratic algorithm, but in practice these stacks
 240                                 // are extremely short (bounded by the nesting depth of interface
 241                                 // type declarations that recur via parameter types, an extremely
 242                                 // rare occurrence). An alternative implementation might use a
 243                                 // "visited" map, but that is probably less efficient overall.
 244                                 q := &ifacePair{x, y, p}
 245                                 for p != nil {
 246                                         if p.identical(q) {
 247                                                 return true // same pair was compared before
 248                                         }
 249                                         p = p.prev
 250                                 }
 251                                 if debug {
 252                                         assert(sort.IsSorted(byUniqueMethodName(a)))
 253                                         assert(sort.IsSorted(byUniqueMethodName(b)))
 254                                 }
 255                                 for i, f := range a {
 256                                         g := b[i]
 257                                         if f.Id() != g.Id() || !identical(f.typ, g.typ, cmpTags, q) {
 258                                                 return false
 259                                         }
 260                                 }
 261                                 return true
 262                         }
 263                 }
 264
 265         case *Map:
 266                 // Two map types are identical if they have identical key and value types.
 267                 if y, ok := y.(*Map); ok {
 268                         return identical(x.key, y.key, cmpTags, p) && identical(x.elem, y.elem, cmpTags, p)
 269                 }
 270
 271         case *Chan:
 272                 // Two channel types are identical if they have identical value types
 273                 // and the same direction.
 274                 if y, ok := y.(*Chan); ok {
 275                         return x.dir == y.dir && identical(x.elem, y.elem, cmpTags, p)
 276                 }
 277
 278         case *Named:
 279                 // Two named types are identical if their type names originate
 280                 // in the same type declaration.
 281                 if y, ok := y.(*Named); ok {
 282                         return x.obj == y.obj
 283                 }
 284
 285         case nil:
 286
 287         default:
 288                 unreachable()
 289         }
 290
 291         return false
 292 }
 293
 294 // Default returns the default "typed" type for an "untyped" type;
 295 // it returns the incoming type for all other types. The default type
 296 // for untyped nil is untyped nil.
 297 //
 298 func Default(typ Type) Type {
 299         if t, ok := typ.(*Basic); ok {
 300                 switch t.kind {
 301                 case UntypedBool:
 302                         return Typ[Bool]
 303                 case UntypedInt:
 304                         return Typ[Int]
 305                 case UntypedRune:
 306                         return universeRune // use 'rune' name
 307                 case UntypedFloat:
 308                         return Typ[Float64]
 309                 case UntypedComplex:
 310                         return Typ[Complex128]
 311                 case UntypedString:
 312                         return Typ[String]
 313                 }
 314         }
 315         return typ
 316 }