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 "go/token" 10 11// The isX predicates below report whether t is an X. 12// If t is a type parameter the result is false; i.e., 13// these predicates don't look inside a type parameter. 14 15func isBoolean(t Type) bool { return isBasic(t, IsBoolean) } 16func isInteger(t Type) bool { return isBasic(t, IsInteger) } 17func isUnsigned(t Type) bool { return isBasic(t, IsUnsigned) } 18func isFloat(t Type) bool { return isBasic(t, IsFloat) } 19func isComplex(t Type) bool { return isBasic(t, IsComplex) } 20func isNumeric(t Type) bool { return isBasic(t, IsNumeric) } 21func isString(t Type) bool { return isBasic(t, IsString) } 22func isIntegerOrFloat(t Type) bool { return isBasic(t, IsInteger|IsFloat) } 23func isConstType(t Type) bool { return isBasic(t, IsConstType) } 24 25// isBasic reports whether under(t) is a basic type with the specified info. 26// If t is a type parameter the result is false; i.e., 27// isBasic does not look inside a type parameter. 28func isBasic(t Type, info BasicInfo) bool { 29 u, _ := under(t).(*Basic) 30 return u != nil && u.info&info != 0 31} 32 33// The allX predicates below report whether t is an X. 34// If t is a type parameter the result is true if isX is true 35// for all specified types of the type parameter's type set. 36// allX is an optimized version of isX(structuralType(t)) (which 37// is the same as underIs(t, isX)). 38 39func allBoolean(typ Type) bool { return allBasic(typ, IsBoolean) } 40func allInteger(typ Type) bool { return allBasic(typ, IsInteger) } 41func allUnsigned(typ Type) bool { return allBasic(typ, IsUnsigned) } 42func allNumeric(typ Type) bool { return allBasic(typ, IsNumeric) } 43func allString(typ Type) bool { return allBasic(typ, IsString) } 44func allOrdered(typ Type) bool { return allBasic(typ, IsOrdered) } 45func allNumericOrString(typ Type) bool { return allBasic(typ, IsNumeric|IsString) } 46 47// allBasic reports whether under(t) is a basic type with the specified info. 48// If t is a type parameter, the result is true if isBasic(t, info) is true 49// for all specific types of the type parameter's type set. 50// allBasic(t, info) is an optimized version of isBasic(structuralType(t), info). 51func allBasic(t Type, info BasicInfo) bool { 52 if tpar, _ := t.(*TypeParam); tpar != nil { 53 return tpar.is(func(t *term) bool { return t != nil && isBasic(t.typ, info) }) 54 } 55 return isBasic(t, info) 56} 57 58// hasName reports whether t has a name. This includes 59// predeclared types, defined types, and type parameters. 60// hasName may be called with types that are not fully set up. 61func hasName(t Type) bool { 62 switch t.(type) { 63 case *Basic, *Named, *TypeParam: 64 return true 65 } 66 return false 67} 68 69// isTyped reports whether t is typed; i.e., not an untyped 70// constant or boolean. isTyped may be called with types that 71// are not fully set up. 72func isTyped(t Type) bool { 73 // isTyped is called with types that are not fully 74 // set up. Must not call under()! 75 b, _ := t.(*Basic) 76 return b == nil || b.info&IsUntyped == 0 77} 78 79// isUntyped(t) is the same as !isTyped(t). 80func isUntyped(t Type) bool { 81 return !isTyped(t) 82} 83 84// IsInterface reports whether t is an interface type. 85func IsInterface(t Type) bool { 86 _, ok := under(t).(*Interface) 87 return ok 88} 89 90// isTypeParam reports whether t is a type parameter. 91func isTypeParam(t Type) bool { 92 _, ok := t.(*TypeParam) 93 return ok 94} 95 96// isGeneric reports whether a type is a generic, uninstantiated type 97// (generic signatures are not included). 98// TODO(gri) should we include signatures or assert that they are not present? 99func isGeneric(t Type) bool { 100 // A parameterized type is only generic if it doesn't have an instantiation already. 101 named, _ := t.(*Named) 102 return named != nil && named.obj != nil && named.targs == nil && named.TypeParams() != nil 103} 104 105// Comparable reports whether values of type T are comparable. 106func Comparable(T Type) bool { 107 return comparable(T, nil) 108} 109 110func comparable(T Type, seen map[Type]bool) bool { 111 if seen[T] { 112 return true 113 } 114 if seen == nil { 115 seen = make(map[Type]bool) 116 } 117 seen[T] = true 118 119 switch t := under(T).(type) { 120 case *Basic: 121 // assume invalid types to be comparable 122 // to avoid follow-up errors 123 return t.kind != UntypedNil 124 case *Pointer, *Chan: 125 return true 126 case *Struct: 127 for _, f := range t.fields { 128 if !comparable(f.typ, seen) { 129 return false 130 } 131 } 132 return true 133 case *Array: 134 return comparable(t.elem, seen) 135 case *Interface: 136 return !isTypeParam(T) || t.IsComparable() 137 } 138 return false 139} 140 141// hasNil reports whether type t includes the nil value. 142func hasNil(t Type) bool { 143 switch u := under(t).(type) { 144 case *Basic: 145 return u.kind == UnsafePointer 146 case *Slice, *Pointer, *Signature, *Map, *Chan: 147 return true 148 case *Interface: 149 return !isTypeParam(t) || u.typeSet().underIs(func(u Type) bool { 150 return u != nil && hasNil(u) 151 }) 152 } 153 return false 154} 155 156// An ifacePair is a node in a stack of interface type pairs compared for identity. 157type ifacePair struct { 158 x, y *Interface 159 prev *ifacePair 160} 161 162func (p *ifacePair) identical(q *ifacePair) bool { 163 return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x 164} 165 166// For changes to this code the corresponding changes should be made to unifier.nify. 167func identical(x, y Type, cmpTags bool, p *ifacePair) bool { 168 if x == y { 169 return true 170 } 171 172 switch x := x.(type) { 173 case *Basic: 174 // Basic types are singletons except for the rune and byte 175 // aliases, thus we cannot solely rely on the x == y check 176 // above. See also comment in TypeName.IsAlias. 177 if y, ok := y.(*Basic); ok { 178 return x.kind == y.kind 179 } 180 181 case *Array: 182 // Two array types are identical if they have identical element types 183 // and the same array length. 184 if y, ok := y.(*Array); ok { 185 // If one or both array lengths are unknown (< 0) due to some error, 186 // assume they are the same to avoid spurious follow-on errors. 187 return (x.len < 0 || y.len < 0 || x.len == y.len) && identical(x.elem, y.elem, cmpTags, p) 188 } 189 190 case *Slice: 191 // Two slice types are identical if they have identical element types. 192 if y, ok := y.(*Slice); ok { 193 return identical(x.elem, y.elem, cmpTags, p) 194 } 195 196 case *Struct: 197 // Two struct types are identical if they have the same sequence of fields, 198 // and if corresponding fields have the same names, and identical types, 199 // and identical tags. Two embedded fields are considered to have the same 200 // name. Lower-case field names from different packages are always different. 201 if y, ok := y.(*Struct); ok { 202 if x.NumFields() == y.NumFields() { 203 for i, f := range x.fields { 204 g := y.fields[i] 205 if f.embedded != g.embedded || 206 cmpTags && x.Tag(i) != y.Tag(i) || 207 !f.sameId(g.pkg, g.name) || 208 !identical(f.typ, g.typ, cmpTags, p) { 209 return false 210 } 211 } 212 return true 213 } 214 } 215 216 case *Pointer: 217 // Two pointer types are identical if they have identical base types. 218 if y, ok := y.(*Pointer); ok { 219 return identical(x.base, y.base, cmpTags, p) 220 } 221 222 case *Tuple: 223 // Two tuples types are identical if they have the same number of elements 224 // and corresponding elements have identical types. 225 if y, ok := y.(*Tuple); ok { 226 if x.Len() == y.Len() { 227 if x != nil { 228 for i, v := range x.vars { 229 w := y.vars[i] 230 if !identical(v.typ, w.typ, cmpTags, p) { 231 return false 232 } 233 } 234 } 235 return true 236 } 237 } 238 239 case *Signature: 240 y, _ := y.(*Signature) 241 if y == nil { 242 return false 243 } 244 245 // Two function types are identical if they have the same number of 246 // parameters and result values, corresponding parameter and result types 247 // are identical, and either both functions are variadic or neither is. 248 // Parameter and result names are not required to match, and type 249 // parameters are considered identical modulo renaming. 250 251 if x.TypeParams().Len() != y.TypeParams().Len() { 252 return false 253 } 254 255 // In the case of generic signatures, we will substitute in yparams and 256 // yresults. 257 yparams := y.params 258 yresults := y.results 259 260 if x.TypeParams().Len() > 0 { 261 // We must ignore type parameter names when comparing x and y. The 262 // easiest way to do this is to substitute x's type parameters for y's. 263 xtparams := x.TypeParams().list() 264 ytparams := y.TypeParams().list() 265 266 var targs []Type 267 for i := range xtparams { 268 targs = append(targs, x.TypeParams().At(i)) 269 } 270 smap := makeSubstMap(ytparams, targs) 271 272 var check *Checker // ok to call subst on a nil *Checker 273 274 // Constraints must be pair-wise identical, after substitution. 275 for i, xtparam := range xtparams { 276 ybound := check.subst(token.NoPos, ytparams[i].bound, smap, nil) 277 if !identical(xtparam.bound, ybound, cmpTags, p) { 278 return false 279 } 280 } 281 282 yparams = check.subst(token.NoPos, y.params, smap, nil).(*Tuple) 283 yresults = check.subst(token.NoPos, y.results, smap, nil).(*Tuple) 284 } 285 286 return x.variadic == y.variadic && 287 identical(x.params, yparams, cmpTags, p) && 288 identical(x.results, yresults, cmpTags, p) 289 290 case *Union: 291 if y, _ := y.(*Union); y != nil { 292 xset := computeUnionTypeSet(nil, token.NoPos, x) 293 yset := computeUnionTypeSet(nil, token.NoPos, y) 294 return xset.terms.equal(yset.terms) 295 } 296 297 case *Interface: 298 // Two interface types are identical if they describe the same type sets. 299 // With the existing implementation restriction, this simplifies to: 300 // 301 // Two interface types are identical if they have the same set of methods with 302 // the same names and identical function types, and if any type restrictions 303 // are the same. Lower-case method names from different packages are always 304 // different. The order of the methods is irrelevant. 305 if y, ok := y.(*Interface); ok { 306 xset := x.typeSet() 307 yset := y.typeSet() 308 if !xset.terms.equal(yset.terms) { 309 return false 310 } 311 a := xset.methods 312 b := yset.methods 313 if len(a) == len(b) { 314 // Interface types are the only types where cycles can occur 315 // that are not "terminated" via named types; and such cycles 316 // can only be created via method parameter types that are 317 // anonymous interfaces (directly or indirectly) embedding 318 // the current interface. Example: 319 // 320 // type T interface { 321 // m() interface{T} 322 // } 323 // 324 // If two such (differently named) interfaces are compared, 325 // endless recursion occurs if the cycle is not detected. 326 // 327 // If x and y were compared before, they must be equal 328 // (if they were not, the recursion would have stopped); 329 // search the ifacePair stack for the same pair. 330 // 331 // This is a quadratic algorithm, but in practice these stacks 332 // are extremely short (bounded by the nesting depth of interface 333 // type declarations that recur via parameter types, an extremely 334 // rare occurrence). An alternative implementation might use a 335 // "visited" map, but that is probably less efficient overall. 336 q := &ifacePair{x, y, p} 337 for p != nil { 338 if p.identical(q) { 339 return true // same pair was compared before 340 } 341 p = p.prev 342 } 343 if debug { 344 assertSortedMethods(a) 345 assertSortedMethods(b) 346 } 347 for i, f := range a { 348 g := b[i] 349 if f.Id() != g.Id() || !identical(f.typ, g.typ, cmpTags, q) { 350 return false 351 } 352 } 353 return true 354 } 355 } 356 357 case *Map: 358 // Two map types are identical if they have identical key and value types. 359 if y, ok := y.(*Map); ok { 360 return identical(x.key, y.key, cmpTags, p) && identical(x.elem, y.elem, cmpTags, p) 361 } 362 363 case *Chan: 364 // Two channel types are identical if they have identical value types 365 // and the same direction. 366 if y, ok := y.(*Chan); ok { 367 return x.dir == y.dir && identical(x.elem, y.elem, cmpTags, p) 368 } 369 370 case *Named: 371 // Two named types are identical if their type names originate 372 // in the same type declaration. 373 if y, ok := y.(*Named); ok { 374 xargs := x.TypeArgs().list() 375 yargs := y.TypeArgs().list() 376 377 if len(xargs) != len(yargs) { 378 return false 379 } 380 381 if len(xargs) > 0 { 382 // Instances are identical if their original type and type arguments 383 // are identical. 384 if !Identical(x.orig, y.orig) { 385 return false 386 } 387 for i, xa := range xargs { 388 if !Identical(xa, yargs[i]) { 389 return false 390 } 391 } 392 return true 393 } 394 395 // TODO(gri) Why is x == y not sufficient? And if it is, 396 // we can just return false here because x == y 397 // is caught in the very beginning of this function. 398 return x.obj == y.obj 399 } 400 401 case *TypeParam: 402 // nothing to do (x and y being equal is caught in the very beginning of this function) 403 404 case nil: 405 // avoid a crash in case of nil type 406 407 default: 408 unreachable() 409 } 410 411 return false 412} 413 414// identicalInstance reports if two type instantiations are identical. 415// Instantiations are identical if their origin and type arguments are 416// identical. 417func identicalInstance(xorig Type, xargs []Type, yorig Type, yargs []Type) bool { 418 if len(xargs) != len(yargs) { 419 return false 420 } 421 422 for i, xa := range xargs { 423 if !Identical(xa, yargs[i]) { 424 return false 425 } 426 } 427 428 return Identical(xorig, yorig) 429} 430 431// Default returns the default "typed" type for an "untyped" type; 432// it returns the incoming type for all other types. The default type 433// for untyped nil is untyped nil. 434func Default(t Type) Type { 435 if t, ok := t.(*Basic); ok { 436 switch t.kind { 437 case UntypedBool: 438 return Typ[Bool] 439 case UntypedInt: 440 return Typ[Int] 441 case UntypedRune: 442 return universeRune // use 'rune' name 443 case UntypedFloat: 444 return Typ[Float64] 445 case UntypedComplex: 446 return Typ[Complex128] 447 case UntypedString: 448 return Typ[String] 449 } 450 } 451 return t 452} 453