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 7package types 8 9import ( 10 "go/token" 11) 12 13// isNamed reports whether typ has a name. 14// isNamed may be called with types that are not fully set up. 15func isNamed(typ Type) bool { 16 switch typ.(type) { 17 case *Basic, *Named, *_TypeParam, *instance: 18 return true 19 } 20 return false 21} 22 23// isGeneric reports whether a type is a generic, uninstantiated type (generic 24// signatures are not included). 25func isGeneric(typ Type) bool { 26 // A parameterized type is only instantiated if it doesn't have an instantiation already. 27 named, _ := typ.(*Named) 28 return named != nil && named.obj != nil && named.tparams != nil && named.targs == nil 29} 30 31func is(typ Type, what BasicInfo) bool { 32 switch t := optype(typ).(type) { 33 case *Basic: 34 return t.info&what != 0 35 case *_Sum: 36 return t.is(func(typ Type) bool { return is(typ, what) }) 37 } 38 return false 39} 40 41func isBoolean(typ Type) bool { return is(typ, IsBoolean) } 42func isInteger(typ Type) bool { return is(typ, IsInteger) } 43func isUnsigned(typ Type) bool { return is(typ, IsUnsigned) } 44func isFloat(typ Type) bool { return is(typ, IsFloat) } 45func isComplex(typ Type) bool { return is(typ, IsComplex) } 46func isNumeric(typ Type) bool { return is(typ, IsNumeric) } 47func isString(typ Type) bool { return is(typ, IsString) } 48 49// Note that if typ is a type parameter, isInteger(typ) || isFloat(typ) does not 50// produce the expected result because a type list that contains both an integer 51// and a floating-point type is neither (all) integers, nor (all) floats. 52// Use isIntegerOrFloat instead. 53func isIntegerOrFloat(typ Type) bool { return is(typ, IsInteger|IsFloat) } 54 55// isNumericOrString is the equivalent of isIntegerOrFloat for isNumeric(typ) || isString(typ). 56func isNumericOrString(typ Type) bool { return is(typ, IsNumeric|IsString) } 57 58// isTyped reports whether typ is typed; i.e., not an untyped 59// constant or boolean. isTyped may be called with types that 60// are not fully set up. 61func isTyped(typ Type) bool { 62 // isTyped is called with types that are not fully 63 // set up. Must not call asBasic()! 64 // A *Named or *instance type is always typed, so 65 // we only need to check if we have a true *Basic 66 // type. 67 t, _ := typ.(*Basic) 68 return t == nil || t.info&IsUntyped == 0 69} 70 71// isUntyped(typ) is the same as !isTyped(typ). 72func isUntyped(typ Type) bool { 73 return !isTyped(typ) 74} 75 76func isOrdered(typ Type) bool { return is(typ, IsOrdered) } 77 78func isConstType(typ Type) bool { 79 // Type parameters are never const types. 80 t, _ := under(typ).(*Basic) 81 return t != nil && t.info&IsConstType != 0 82} 83 84// IsInterface reports whether typ is an interface type. 85func IsInterface(typ Type) bool { 86 return asInterface(typ) != nil 87} 88 89// Comparable reports whether values of type T are comparable. 90func Comparable(T Type) bool { 91 return comparable(T, nil) 92} 93 94func comparable(T Type, seen map[Type]bool) bool { 95 if seen[T] { 96 return true 97 } 98 if seen == nil { 99 seen = make(map[Type]bool) 100 } 101 seen[T] = true 102 103 // If T is a type parameter not constrained by any type 104 // list (i.e., it's underlying type is the top type), 105 // T is comparable if it has the == method. Otherwise, 106 // the underlying type "wins". For instance 107 // 108 // interface{ comparable; type []byte } 109 // 110 // is not comparable because []byte is not comparable. 111 if t := asTypeParam(T); t != nil && optype(t) == theTop { 112 return t.Bound()._IsComparable() 113 } 114 115 switch t := optype(T).(type) { 116 case *Basic: 117 // assume invalid types to be comparable 118 // to avoid follow-up errors 119 return t.kind != UntypedNil 120 case *Pointer, *Interface, *Chan: 121 return true 122 case *Struct: 123 for _, f := range t.fields { 124 if !comparable(f.typ, seen) { 125 return false 126 } 127 } 128 return true 129 case *Array: 130 return comparable(t.elem, seen) 131 case *_Sum: 132 pred := func(t Type) bool { 133 return comparable(t, seen) 134 } 135 return t.is(pred) 136 case *_TypeParam: 137 return t.Bound()._IsComparable() 138 } 139 return false 140} 141 142// hasNil reports whether a type includes the nil value. 143func hasNil(typ Type) bool { 144 switch t := optype(typ).(type) { 145 case *Basic: 146 return t.kind == UnsafePointer 147 case *Slice, *Pointer, *Signature, *Interface, *Map, *Chan: 148 return true 149 case *_Sum: 150 return t.is(hasNil) 151 } 152 return false 153} 154 155// identical reports whether x and y are identical types. 156// Receivers of Signature types are ignored. 157func (check *Checker) identical(x, y Type) bool { 158 return check.identical0(x, y, true, nil) 159} 160 161// identicalIgnoreTags reports whether x and y are identical types if tags are ignored. 162// Receivers of Signature types are ignored. 163func (check *Checker) identicalIgnoreTags(x, y Type) bool { 164 return check.identical0(x, y, false, nil) 165} 166 167// An ifacePair is a node in a stack of interface type pairs compared for identity. 168type ifacePair struct { 169 x, y *Interface 170 prev *ifacePair 171} 172 173func (p *ifacePair) identical(q *ifacePair) bool { 174 return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x 175} 176 177// For changes to this code the corresponding changes should be made to unifier.nify. 178func (check *Checker) identical0(x, y Type, cmpTags bool, p *ifacePair) bool { 179 // types must be expanded for comparison 180 x = expandf(x) 181 y = expandf(y) 182 183 if x == y { 184 return true 185 } 186 187 switch x := x.(type) { 188 case *Basic: 189 // Basic types are singletons except for the rune and byte 190 // aliases, thus we cannot solely rely on the x == y check 191 // above. See also comment in TypeName.IsAlias. 192 if y, ok := y.(*Basic); ok { 193 return x.kind == y.kind 194 } 195 196 case *Array: 197 // Two array types are identical if they have identical element types 198 // and the same array length. 199 if y, ok := y.(*Array); ok { 200 // If one or both array lengths are unknown (< 0) due to some error, 201 // assume they are the same to avoid spurious follow-on errors. 202 return (x.len < 0 || y.len < 0 || x.len == y.len) && check.identical0(x.elem, y.elem, cmpTags, p) 203 } 204 205 case *Slice: 206 // Two slice types are identical if they have identical element types. 207 if y, ok := y.(*Slice); ok { 208 return check.identical0(x.elem, y.elem, cmpTags, p) 209 } 210 211 case *Struct: 212 // Two struct types are identical if they have the same sequence of fields, 213 // and if corresponding fields have the same names, and identical types, 214 // and identical tags. Two embedded fields are considered to have the same 215 // name. Lower-case field names from different packages are always different. 216 if y, ok := y.(*Struct); ok { 217 if x.NumFields() == y.NumFields() { 218 for i, f := range x.fields { 219 g := y.fields[i] 220 if f.embedded != g.embedded || 221 cmpTags && x.Tag(i) != y.Tag(i) || 222 !f.sameId(g.pkg, g.name) || 223 !check.identical0(f.typ, g.typ, cmpTags, p) { 224 return false 225 } 226 } 227 return true 228 } 229 } 230 231 case *Pointer: 232 // Two pointer types are identical if they have identical base types. 233 if y, ok := y.(*Pointer); ok { 234 return check.identical0(x.base, y.base, cmpTags, p) 235 } 236 237 case *Tuple: 238 // Two tuples types are identical if they have the same number of elements 239 // and corresponding elements have identical types. 240 if y, ok := y.(*Tuple); ok { 241 if x.Len() == y.Len() { 242 if x != nil { 243 for i, v := range x.vars { 244 w := y.vars[i] 245 if !check.identical0(v.typ, w.typ, cmpTags, p) { 246 return false 247 } 248 } 249 } 250 return true 251 } 252 } 253 254 case *Signature: 255 // Two function types are identical if they have the same number of parameters 256 // and result values, corresponding parameter and result types are identical, 257 // and either both functions are variadic or neither is. Parameter and result 258 // names are not required to match. 259 // Generic functions must also have matching type parameter lists, but for the 260 // parameter names. 261 if y, ok := y.(*Signature); ok { 262 return x.variadic == y.variadic && 263 check.identicalTParams(x.tparams, y.tparams, cmpTags, p) && 264 check.identical0(x.params, y.params, cmpTags, p) && 265 check.identical0(x.results, y.results, cmpTags, p) 266 } 267 268 case *_Sum: 269 // Two sum types are identical if they contain the same types. 270 // (Sum types always consist of at least two types. Also, the 271 // the set (list) of types in a sum type consists of unique 272 // types - each type appears exactly once. Thus, two sum types 273 // must contain the same number of types to have chance of 274 // being equal. 275 if y, ok := y.(*_Sum); ok && len(x.types) == len(y.types) { 276 // Every type in x.types must be in y.types. 277 // Quadratic algorithm, but probably good enough for now. 278 // TODO(gri) we need a fast quick type ID/hash for all types. 279 L: 280 for _, x := range x.types { 281 for _, y := range y.types { 282 if Identical(x, y) { 283 continue L // x is in y.types 284 } 285 } 286 return false // x is not in y.types 287 } 288 return true 289 } 290 291 case *Interface: 292 // Two interface types are identical if they have the same set of methods with 293 // the same names and identical function types. Lower-case method names from 294 // different packages are always different. The order of the methods is irrelevant. 295 if y, ok := y.(*Interface); ok { 296 // If identical0 is called (indirectly) via an external API entry point 297 // (such as Identical, IdenticalIgnoreTags, etc.), check is nil. But in 298 // that case, interfaces are expected to be complete and lazy completion 299 // here is not needed. 300 if check != nil { 301 check.completeInterface(token.NoPos, x) 302 check.completeInterface(token.NoPos, y) 303 } 304 a := x.allMethods 305 b := y.allMethods 306 if len(a) == len(b) { 307 // Interface types are the only types where cycles can occur 308 // that are not "terminated" via named types; and such cycles 309 // can only be created via method parameter types that are 310 // anonymous interfaces (directly or indirectly) embedding 311 // the current interface. Example: 312 // 313 // type T interface { 314 // m() interface{T} 315 // } 316 // 317 // If two such (differently named) interfaces are compared, 318 // endless recursion occurs if the cycle is not detected. 319 // 320 // If x and y were compared before, they must be equal 321 // (if they were not, the recursion would have stopped); 322 // search the ifacePair stack for the same pair. 323 // 324 // This is a quadratic algorithm, but in practice these stacks 325 // are extremely short (bounded by the nesting depth of interface 326 // type declarations that recur via parameter types, an extremely 327 // rare occurrence). An alternative implementation might use a 328 // "visited" map, but that is probably less efficient overall. 329 q := &ifacePair{x, y, p} 330 for p != nil { 331 if p.identical(q) { 332 return true // same pair was compared before 333 } 334 p = p.prev 335 } 336 if debug { 337 assertSortedMethods(a) 338 assertSortedMethods(b) 339 } 340 for i, f := range a { 341 g := b[i] 342 if f.Id() != g.Id() || !check.identical0(f.typ, g.typ, cmpTags, q) { 343 return false 344 } 345 } 346 return true 347 } 348 } 349 350 case *Map: 351 // Two map types are identical if they have identical key and value types. 352 if y, ok := y.(*Map); ok { 353 return check.identical0(x.key, y.key, cmpTags, p) && check.identical0(x.elem, y.elem, cmpTags, p) 354 } 355 356 case *Chan: 357 // Two channel types are identical if they have identical value types 358 // and the same direction. 359 if y, ok := y.(*Chan); ok { 360 return x.dir == y.dir && check.identical0(x.elem, y.elem, cmpTags, p) 361 } 362 363 case *Named: 364 // Two named types are identical if their type names originate 365 // in the same type declaration. 366 if y, ok := y.(*Named); ok { 367 // TODO(gri) Why is x == y not sufficient? And if it is, 368 // we can just return false here because x == y 369 // is caught in the very beginning of this function. 370 return x.obj == y.obj 371 } 372 373 case *_TypeParam: 374 // nothing to do (x and y being equal is caught in the very beginning of this function) 375 376 // case *instance: 377 // unreachable since types are expanded 378 379 case *bottom, *top: 380 // Either both types are theBottom, or both are theTop in which 381 // case the initial x == y check will have caught them. Otherwise 382 // they are not identical. 383 384 case nil: 385 // avoid a crash in case of nil type 386 387 default: 388 unreachable() 389 } 390 391 return false 392} 393 394func (check *Checker) identicalTParams(x, y []*TypeName, cmpTags bool, p *ifacePair) bool { 395 if len(x) != len(y) { 396 return false 397 } 398 for i, x := range x { 399 y := y[i] 400 if !check.identical0(x.typ.(*_TypeParam).bound, y.typ.(*_TypeParam).bound, cmpTags, p) { 401 return false 402 } 403 } 404 return true 405} 406 407// Default returns the default "typed" type for an "untyped" type; 408// it returns the incoming type for all other types. The default type 409// for untyped nil is untyped nil. 410// 411func Default(typ Type) Type { 412 if t, ok := typ.(*Basic); ok { 413 switch t.kind { 414 case UntypedBool: 415 return Typ[Bool] 416 case UntypedInt: 417 return Typ[Int] 418 case UntypedRune: 419 return universeRune // use 'rune' name 420 case UntypedFloat: 421 return Typ[Float64] 422 case UntypedComplex: 423 return Typ[Complex128] 424 case UntypedString: 425 return Typ[String] 426 } 427 } 428 return typ 429} 430